QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218728 | #6101. Ring Road | 275307894a | RE | 0ms | 0kb | C++14 | 2.6kb | 2023-10-18 17:42:43 | 2023-10-18 17:42:43 |
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__uint128_t;
const int N=3e5+5,M=N*8+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,fa[N];ll w[N];vector<pair<int,ll> > S[N];vector<int> G[N],son[N];
vector<pii> q[N];ll ans[N];
void con(int x,int y){S[x].eb(y,w[y]);S[y].eb(x,w[y]);G[x].eb(y);G[y].eb(x);}
int Ct,f[N],siz[N],vis[N],col[N],Rt;
ll d[N];
vector<int> scc;
void dij(int x){
for(int i:scc) d[i]=1e18;d[x]=0;
priority_queue<pair<ll,int> > Q;Q.emplace(0,x);
while(!Q.empty()){
auto p=Q.top();Q.pop();p.fi*=-1;if(p.fi^d[p.se]) continue;
for(auto i:S[p.se]) if(col[i.fi]==col[x]&&d[i.fi]>i.se+p.fi) d[i.fi]=i.se+p.fi,Q.emplace(-d[i.fi],i.fi);
}
for(int i:scc) for(auto j:q[i]) if(col[j.fi]==col[i]) ans[j.se]=min(ans[j.se],d[i]+d[j.fi]);
}
void GI(int x,int La){scc.eb(x);siz[x]=1;col[x]=Rt;for(int i:G[x]) if(i^La&&!vis[i]) GI(i,x),siz[x]+=siz[i];}
void DP(int x,int La){f[x]=Ct-siz[x];for(int i:G[x]) if(i^La&&!vis[i]) f[x]=max(f[x],siz[i]),DP(i,x);if(f[Rt]>f[x]) Rt=x;}
int search(int x,int La){
if(son[x].empty()&&x<=n) return x;
int ans=-INF;for(int i:G[x]) if(!vis[i]&&i^La) ans=max(ans,search(i,x));
return ans;
}
void dfs(int x){
scc.clear();Rt=++m;GI(x,0);Ct=siz[x];f[Rt=0]=INF;DP(x,0);vis[x=Rt]=1;
dij(x);
for(int i:G[x]) if(!vis[i]) {
int p=search(i,x);
if(p<=n) dij(p);
}
for(int i:G[x]) if(!vis[i]) dfs(i);
}
void Solve(){
int i,j;scanf("%d",&n);
for(i=2;i<=n;i++) scanf("%d%lld",&fa[i],&w[i]),son[fa[i]].eb(i);
m=n;for(i=1;i<=n;i++) if(!son[i].empty()){
con(i,son[i][0]);if(son[i].size()==1) continue;
int LA=i;
for(j=1;j<son[i].size()-1;j++){
int p=++m;con(LA,p);con(p,son[i][j]);LA=p;
}
con(LA,son[i].back());
}
vector<int> leaf;
for(i=1;i<=n;i++) if(son[i].empty()) leaf.eb(i);leaf.eb(leaf.front());
for(i=1;i<leaf.size();i++) {ll y;scanf("%lld",&y);S[leaf[i]].eb(leaf[i-1],y);S[leaf[i-1]].eb(leaf[i],y);}
int Q;scanf("%d",&Q);for(i=1;i<=Q;i++){int x,y;scanf("%d%d",&x,&y);q[x].eb(y,i);q[y].eb(x,i);ans[i]=1e18;}
dfs(1);for(i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 1 9 1 8 1 0 9 9 9 6 1 2 1 3 1 4 2 3 2 4 3 4