結果
| 問題 | 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 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;
}