結果
問題 | No.1212 Second Path |
ユーザー | 沙耶花 |
提出日時 | 2020-08-30 17:42:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,345 ms / 3,000 ms |
コード長 | 5,639 bytes |
コンパイル時間 | 3,275 ms |
コンパイル使用メモリ | 250,104 KB |
実行使用メモリ | 208,492 KB |
最終ジャッジ日時 | 2024-04-27 12:27:55 |
合計ジャッジ時間 | 39,192 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,007 ms
208,336 KB |
testcase_01 | AC | 1,276 ms
208,372 KB |
testcase_02 | AC | 1,323 ms
208,376 KB |
testcase_03 | AC | 1,324 ms
208,388 KB |
testcase_04 | AC | 1,345 ms
208,368 KB |
testcase_05 | AC | 1,309 ms
208,488 KB |
testcase_06 | AC | 494 ms
75,852 KB |
testcase_07 | AC | 953 ms
146,544 KB |
testcase_08 | AC | 925 ms
135,324 KB |
testcase_09 | AC | 912 ms
131,808 KB |
testcase_10 | AC | 938 ms
141,208 KB |
testcase_11 | AC | 918 ms
137,560 KB |
testcase_12 | AC | 935 ms
147,656 KB |
testcase_13 | AC | 915 ms
143,904 KB |
testcase_14 | AC | 896 ms
136,860 KB |
testcase_15 | AC | 915 ms
139,716 KB |
testcase_16 | AC | 936 ms
133,288 KB |
testcase_17 | AC | 1,000 ms
208,300 KB |
testcase_18 | AC | 155 ms
6,944 KB |
testcase_19 | AC | 171 ms
6,944 KB |
testcase_20 | AC | 159 ms
6,940 KB |
testcase_21 | AC | 155 ms
6,940 KB |
testcase_22 | AC | 155 ms
6,944 KB |
testcase_23 | AC | 142 ms
6,944 KB |
testcase_24 | AC | 145 ms
6,940 KB |
testcase_25 | AC | 144 ms
6,940 KB |
testcase_26 | AC | 153 ms
6,944 KB |
testcase_27 | AC | 147 ms
6,940 KB |
testcase_28 | AC | 156 ms
6,940 KB |
testcase_29 | AC | 1,186 ms
208,332 KB |
testcase_30 | AC | 1,195 ms
208,364 KB |
testcase_31 | AC | 1,202 ms
208,492 KB |
testcase_32 | AC | 711 ms
98,904 KB |
testcase_33 | AC | 600 ms
78,556 KB |
testcase_34 | AC | 871 ms
126,236 KB |
testcase_35 | AC | 232 ms
14,336 KB |
testcase_36 | AC | 720 ms
104,372 KB |
testcase_37 | AC | 686 ms
94,684 KB |
testcase_38 | AC | 730 ms
102,644 KB |
testcase_39 | AC | 466 ms
56,780 KB |
testcase_40 | AC | 166 ms
6,940 KB |
testcase_41 | AC | 705 ms
98,312 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,940 KB |
testcase_44 | AC | 1 ms
6,940 KB |
testcase_45 | AC | 486 ms
75,844 KB |
testcase_46 | AC | 494 ms
75,856 KB |
testcase_47 | AC | 503 ms
75,944 KB |
コンパイルメッセージ
main.cpp:71:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 71 | void dfs(auto &E,auto &sz,int now,int p){ | ^~~~ main.cpp:71:26: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 71 | void dfs(auto &E,auto &sz,int now,int p){ | ^~~~ main.cpp:86:19: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 86 | void dfs2(auto &E,int now,int p,int l,long long M){ | ^~~~ main.cpp:241:10: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 241 | void dfs(auto &E,int now,int p){ | ^~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 2000000000000000000 vector<vector<pair<long long,int>>> e; struct Tree{ int G; vector<int> L; vector<int> number; vector<Tree> Ts; vector<vector<pair<long long,int>>> E; vector<long long> mini; vector<int> P; Tree(){ } Tree(vector<vector<pair<long long,int>>> EE){ E = EE; vector<int> sz(E.size(),0); dfs(E,sz,0,-1); //cout<<G<<endl; P.resize(E.size(),-1); L.resize(E.size(),-1); mini.resize(E.size(),Inf); for(int i=0;i<E[G].size();i++){ if(E[G][i].second!=-1)dfs2(E,E[G][i].second,G,i,Inf); } number.resize(E.size(),0); vector<int> t(E[G].size(),0); for(int i=0;i<E.size();i++){ if(L[i]==-1)continue; number[i] = t[L[i]]; t[L[i]]++; } vector<vector<vector<pair<long long,int>>>> nE(E[G].size()); for(int i=0;i<t.size();i++){ nE[i].resize(t[i],vector<pair<long long,int>>()); } for(int i=0;i<E.size();i++){ if(i==G)continue; for(int j=0;j<E[i].size();j++){ int to =E[i][j].second; if(to!=-1&&L[to]!=-1&&L[i]==L[to]){ //cout<<i<<','<<to<<endl; nE[L[i]][number[i]].emplace_back(E[i][j].first,number[to]); } else if(j<3){ //cout<<i<<','<<to<<endl; nE[L[i]][number[i]].emplace_back(E[i][j].first,-1); } } } if(E.size()>2){ Ts.resize(E[G].size()); for(int i=0;i<E[G].size();i++){ if(E[G][i].second==-1)continue; Ts[i] = Tree(nE[i]); } } } void dfs(auto &E,auto &sz,int now,int p){ sz[now] = 1; bool f = true; for(int i=0;i<E[now].size();i++){ int to = E[now][i].second; if(to==-1)continue; if(to==p)continue; dfs(E,sz,to,now); sz[now] += sz[to]; if(sz[to]*2>E.size())f=false; } if((E.size()-sz[now])*2>E.size())f=false; if(f)G = now; } void dfs2(auto &E,int now,int p,int l,long long M){ mini[now] = M; P[now] = p; multiset<pair<long long,int>> S; for(int i=0;i<E[now].size();i++){ int to = E[now][i].second; if(to==p)continue; S.insert(E[now][i]); } L[now] = l; for(int i=0;i<E[now].size();i++){ int to = E[now][i].second; if(to==-1)continue; if(to==p)continue; long long t = Inf; auto it = S.begin(); if(it->second==to)it++; if(it!=S.end()){ t = it->first; } dfs2(E,to,now,l,min(M,t)); } } long long get(int u,int v){ if(u!=G&&v!=G&&L[u]==L[v]){ return Ts[L[u]].get(number[u],number[v]); } if(v==G)swap(u,v); long long ret = Inf; if(u!=G){ for(int i=0;i<E[u].size();i++){ if(i==3)break; int to = E[u][i].second; if(to==P[u])continue; ret = min(ret,E[u][i].first); } for(int i=0;i<E[v].size();i++){ if(i==3)break; int to = E[v][i].second; if(to==P[v])continue; ret = min(ret,E[v][i].first); } ret = min(ret,mini[u]); ret = min(ret,mini[v]); } else{ for(int i=0;i<E[u].size();i++){ if(i==3)break; int to = E[u][i].second; if(to==-1)continue; if(L[v]==L[to])continue; ret = min(ret,E[u][i].first); } for(int i=0;i<E[v].size();i++){ if(i==3)break; int to = E[v][i].second; if(to==P[v])continue; ret = min(ret,E[v][i].first); } ret = min(ret,mini[v]); } for(int i=0;i<E[G].size();i++){ if(i==3)break; int to = E[G][i].second; if(to!=-1){ if(L[u]==L[to]||L[v]==L[to])continue; } ret = min(ret,E[G][i].first); } return ret; } }; struct lca{ vector<int> depth;//depth[i] 頂点iの深さ vector<vector<int>> parents;//parents[i][j] 頂点iから2^j個上の親 int max_j = 30; lca(int n,vector<vector<int>> &E){ depth.assign(E.size(),-1); parents.assign(E.size(),vector<int>(max_j,-1)); stack<int> s; s.push(n); depth[n] = 0; while(s.size()!=0){ int k = s.top(); s.pop(); for(int i=0;i<E[k].size();i++){ int x = E[k][i]; if(depth[x]!=-1)continue; s.push(x); depth[x] = depth[k]+1; for(int j=0;j<max_j;j++){ if(j==0){ parents[x][j] = k; } else{ parents[x][j] = parents[parents[x][j-1]][j-1]; } if(parents[x][j] == -1)break; } } } } //頂点uのk番目の親 int kth_parent(int u,int k){ for(int i=0;i<max_j;i++){ if(k==0)break; if(u==-1)break; if(k%2){ u = parents[u][i]; } k/=2; } return u; } int query(int u,int v){ if(depth[u]<depth[v])swap(u,v); u = kth_parent(u,depth[u]-depth[v]); if(u==v){ return u; } for(int i=max_j-1;i>=0;i--){ if(parents[u][i]!=parents[v][i]){ u = parents[u][i]; v = parents[v][i]; } } return parents[u][0]; } int get_distance(int u,int v){ return depth[u]+depth[v]-2*depth[query(u,v)]; } }; vector<long long> dis; void dfs(auto &E,int now,int p){ for(int i=0;i<E[now].size();i++){ int to = E[now][i].second; if(to==p)continue; dis[to] = dis[now] + E[now][i].first; dfs(E,to,now); } } int main(){ int N; cin>>N; e.resize(N,vector<pair<long long,int>>()); vector<vector<int>> ee(N,vector<int>()); for(int i=0;i<N-1;i++){ int u,v,w; cin>>u>>v>>w; u--;v--; e[u].emplace_back(w,v); e[v].emplace_back(w,u); ee[u].push_back(v); ee[v].push_back(u); } for(int i=0;i<N;i++){ sort(e[i].begin(),e[i].end()); } dis.resize(N,0LL); dfs(e,0,-1); Tree T(e); lca L(0,ee); int Q; cin>>Q; for(int i=0;i<Q;i++){ int x,y; scanf("%d %d",&x,&y); x--;y--; long long z = T.get(x,y); //cout<<z<<endl; if(z==Inf)cout<<-1<<endl; else{ long long ans = dis[x] + dis[y] - dis[L.query(x,y)]*2 + z*2; cout<<ans<<endl; } } return 0; }