結果
問題 | No.900 aδδitivee |
ユーザー |
|
提出日時 | 2024-01-07 15:51:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,823 bytes |
コンパイル時間 | 8,104 ms |
コンパイル使用メモリ | 355,828 KB |
実行使用メモリ | 26,416 KB |
最終ジャッジ日時 | 2024-09-27 19:24:52 |
合計ジャッジ時間 | 16,242 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | WA * 27 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i,m,n,k) for (int i = (int)(m); i < (int)(n); i += (int)(k))#define rrep(i,m,n,k) for (int i = (int)(m); i > (int)(n); i += (int)(k))#define ll long long#define list(T,A,N) vector<T> A(N);for(int i=0;i<(int)(N);i++){cin >> A[i];}template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}template<typename T> map<T,int> Counter(vector<T> X){map<T,int> C;for(auto x:X){C[x]++;}; return C;}#define endl "\n"struct HLD{int N;vector<vector<int>> e;vector<int> par;vector<int> sub;vector<int> dist;vector<int> head;vector<int> depth;vector<int> ID;vector<int> HEAD;vector<int> PAR;vector<int> DEPTH;vector<int> SUB;HLD(vector<vector<int>> &_e, int root = 0){e = _e;N = (int)(e.size());par = vector<int> (N,-1);sub = vector<int> (N,-1);dist = vector<int> (N,-1);head = vector<int> (N,-1);depth = vector<int> (N,-1);ID = vector<int> (N,-1);HEAD = vector<int> (N,-1);PAR = vector<int> (N,-1);DEPTH = vector<int> (N,-1);SUB = vector<int> (N,-1);dist[root] = 0;deque<int> v;v.emplace_back(root);int x;while(!v.empty()){x = v.front();v.pop_front();for (auto ix:e[x]){if(dist[ix]!=-1) continue;dist[ix] = dist[x] + 1;v.emplace_back(ix);}}vector<pair<int,int>> H(N);for(int i=0;i<N;i++){H[i] = {-dist[i],i};}sort(H.begin(),H.end());int tmp;for(auto [h,i]:H){tmp = 1;for (auto ix:e[i]){if(sub[ix]==-1) par[i] = ix;else tmp += sub[ix];}sub[i] = tmp;}ID[root] = 0;vector<bool> visited(N,false);HEAD[0] = 0;head[root] = 0;depth[root] = 0;DEPTH[0] = 0;int cnt = 0;v.emplace_back(root);SUB[0] = N;vector<pair<int,int>> h;int flg = 0;int n;while(!v.empty()){x = v.front();v.pop_front();visited[x] = true;ID[x] = cnt;cnt ++;n = (int)e[x].size();h.resize(n);for(int i=0;i<n;i++){h[i] = {sub[e[x][i]],e[x][i]};}sort(h.begin(),h.end());flg = 0;if(x==root){flg = -1;}for(auto [_,ix]:h){flg ++;if(visited[ix]) continue;v.emplace_front(ix);if(flg==n-1){head[ix] = head[x];depth[ix] = depth[x];}else{head[ix] = ix;depth[ix] = depth[x] + 1;}}}for(int i=0;i<N;i++){if(par[i]==-1){PAR[ID[i]] == -1;}else{PAR[ID[i]] = ID[par[i]];}HEAD[ID[i]] = ID[head[i]];DEPTH[ID[i]] = depth[i];SUB[ID[i]] = sub[i];}cout << endl;}vector<pair<int,int>> path_query(int l, int r){int L = ID[l];int R = ID[r];pair<int,int> tmp;vector<pair<int,int>> res;if(DEPTH[L]<DEPTH[R]){L = ID[r];R = ID[l];}while(DEPTH[L]!=DEPTH[R]){tmp = {HEAD[L],L+1};res.emplace_back(tmp);L = PAR[HEAD[L]];}while (HEAD[L]!=HEAD[R]){tmp = {HEAD[L],L+1};res.emplace_back(tmp);tmp = {HEAD[R],R+1};res.emplace_back(tmp);L = PAR[HEAD[L]];R = PAR[HEAD[R]];}tmp = {min(L,R),max(L,R)+1};res.emplace_back(tmp);return res;}pair<int,int> sub_query(int k){int K = ID[k];return {K,K+SUB[K]};}};array<ll,2> ope(array<ll,2> x,array<ll,2> y){array<ll,2> z;z[0] = x[0]+y[0];z[1] = x[1]+y[1];return z;}array<ll,2> e_(){array<ll,2> z={0};return z;}array<ll,2> mapping(ll f, array<ll,2> x){array<ll,2> z;z[0] = x[0]+f*x[1];z[1] = x[1];return z;}ll composition(ll f,ll g){return f+g;}ll id_(){return 0;}int main(){int N;cin >> N;vector<vector<int>> e(N);vector<ll> W(N);int u,v;ll w;rep(_,0,N-1,1){cin >> u >> v >> w;e[u].emplace_back(v);e[v].emplace_back(u);W[v] = w;}int Q;cin >> Q;HLD hld(e);vector<int> id = hld.ID;vector<array<ll,2>> B(N,array<ll,2> {0});rep(i,0,N,1){B[id[i]][0] = W[i];B[id[i]][1] = 1;}lazy_segtree<array<ll,2>,ope,e_,ll,mapping,composition,id_> T(B);int flg,l,r,b,a;ll x,tmp;rep(_,0,Q,1){cin >> flg;if(flg==1){cin >> a >> x;auto [l,r] = hld.sub_query(a);T.apply(l+1,r,x);}else{cin >> b;tmp = 0;for(auto lr:hld.path_query(0,b)){l = lr.first;r = lr.second;tmp += T.prod(l,r)[0];}cout << tmp << endl;}}return 0;}