結果
問題 | No.1212 Second Path |
ユーザー | 沙耶花 |
提出日時 | 2020-08-30 17:42:38 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,407 ms / 3,000 ms |
コード長 | 5,639 bytes |
コンパイル時間 | 4,713 ms |
コンパイル使用メモリ | 246,120 KB |
実行使用メモリ | 208,152 KB |
最終ジャッジ日時 | 2023-08-09 17:41:02 |
合計ジャッジ時間 | 42,236 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,056 ms
207,960 KB |
testcase_01 | AC | 1,360 ms
208,048 KB |
testcase_02 | AC | 1,390 ms
208,152 KB |
testcase_03 | AC | 1,358 ms
208,108 KB |
testcase_04 | AC | 1,393 ms
207,944 KB |
testcase_05 | AC | 1,407 ms
208,036 KB |
testcase_06 | AC | 510 ms
75,620 KB |
testcase_07 | AC | 991 ms
146,364 KB |
testcase_08 | AC | 940 ms
135,132 KB |
testcase_09 | AC | 944 ms
131,476 KB |
testcase_10 | AC | 952 ms
140,948 KB |
testcase_11 | AC | 966 ms
137,348 KB |
testcase_12 | AC | 982 ms
147,524 KB |
testcase_13 | AC | 959 ms
143,508 KB |
testcase_14 | AC | 937 ms
136,696 KB |
testcase_15 | AC | 940 ms
139,436 KB |
testcase_16 | AC | 937 ms
132,900 KB |
testcase_17 | AC | 1,021 ms
208,076 KB |
testcase_18 | AC | 144 ms
4,384 KB |
testcase_19 | AC | 147 ms
4,384 KB |
testcase_20 | AC | 160 ms
4,380 KB |
testcase_21 | AC | 153 ms
4,380 KB |
testcase_22 | AC | 147 ms
4,380 KB |
testcase_23 | AC | 131 ms
4,380 KB |
testcase_24 | AC | 135 ms
4,380 KB |
testcase_25 | AC | 134 ms
4,376 KB |
testcase_26 | AC | 147 ms
4,380 KB |
testcase_27 | AC | 154 ms
4,380 KB |
testcase_28 | AC | 136 ms
4,376 KB |
testcase_29 | AC | 1,233 ms
208,092 KB |
testcase_30 | AC | 1,233 ms
207,996 KB |
testcase_31 | AC | 1,286 ms
207,936 KB |
testcase_32 | AC | 714 ms
98,884 KB |
testcase_33 | AC | 616 ms
78,360 KB |
testcase_34 | AC | 881 ms
126,040 KB |
testcase_35 | AC | 218 ms
14,224 KB |
testcase_36 | AC | 741 ms
104,136 KB |
testcase_37 | AC | 684 ms
94,432 KB |
testcase_38 | AC | 722 ms
102,412 KB |
testcase_39 | AC | 474 ms
56,400 KB |
testcase_40 | AC | 157 ms
4,380 KB |
testcase_41 | AC | 730 ms
98,132 KB |
testcase_42 | AC | 1 ms
4,380 KB |
testcase_43 | AC | 1 ms
4,380 KB |
testcase_44 | AC | 2 ms
4,380 KB |
testcase_45 | AC | 523 ms
75,812 KB |
testcase_46 | AC | 506 ms
75,624 KB |
testcase_47 | AC | 520 ms
75,676 KB |
コンパイルメッセージ
main.cpp:71:18: 警告: 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: 警告: 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: 警告: 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: 警告: 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; }