QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218616 | #6101. Ring Road | 275307894a | WA | 0ms | 40844kb | C++14 | 2.8kb | 2023-10-18 15:53:50 | 2023-10-18 15:53:51 |
Judging History
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);}
void reb(vector<int> son,int x){
if(son.empty()) return;
if(son.size()==1) {con(x,son.back());return;}
int v=++m,Le=son.size()/2;con(x,v);
vector<int> ls(son.begin(),son.begin()+Le),rs(son.begin()+Le,son.end());
reb(ls,m);reb(rs,m);
}
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(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;}
pii search(int x,int La){
if(son[x].empty()&&x<=n) return make_pair(x,x);
pii ans=make_pair(INF,-INF);
for(int i:G[x]) if(!vis[i]&&i^La) {auto p=search(i,x);ans.fi=min(ans.fi,p.fi);ans.se=max(ans.se,p.se);}
return ans;
}
void dfs(int x){
scc.clear();Rt=x;GI(x,0);Ct=siz[x];f[Rt=0]=INF;DP(x,0);vis[x=Rt]=1;if(clock()*1.0/CLOCKS_PER_SEC>2.5) return;
dij(x);assert(G[x].size()<=3);
for(int i:G[x]) if(!vis[i]) {
auto p=search(i,x);
if(p.fi<=n) dij(p.fi);
if(p.se>p.fi) dij(p.se);
}
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++) reb(son[i],i);
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: 100
Accepted
time: 0ms
memory: 34720kb
input:
4 1 9 1 8 1 0 9 9 9 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
9 8 0 9 9 8
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 40844kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 0 0 0 0 0 0 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
7 1 1 0 0 0 0 0 1 0 0 7 1 7 0 0 0 8 1 6 0
result:
wrong answer 2nd numbers differ - expected: '8', found: '1'