結果
問題 | No.1212 Second Path |
ユーザー |
![]() |
提出日時 | 2020-08-30 17:42:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,894 ms / 3,000 ms |
コード長 | 5,639 bytes |
コンパイル時間 | 4,159 ms |
コンパイル使用メモリ | 238,488 KB |
最終ジャッジ日時 | 2025-01-14 01:38:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
コンパイルメッセージ
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){ | ^~~~ main.cpp: In function ‘int main()’: main.cpp:280:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 280 | scanf("%d %d",&x,&y); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 2000000000000000000vector<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;}