QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218614 | #6101. Ring Road | 275307894a | WA | 2518ms | 63752kb | C++14 | 2.8kb | 2023-10-18 15:53:04 | 2023-10-18 15:53:04 |
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){
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: 41016kb
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: 0
Accepted
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 8 8 7 7 7 0 7 1 7 7 7 1 7 0 7 0 8 1 6 0
result:
ok 21 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 40980kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 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:
9 8 8 15 9 14 0 7 1 7 14 9 15 9 22 9 23 8 15 16 16
result:
ok 21 numbers
Test #4:
score: 0
Accepted
time: 2510ms
memory: 63056kb
input:
99998 1 683940 1 335116 3 198362 4 28825 5 625394 6 314200 7 270653 8 61629 9 650997 10 693039 11 159577 12 466708 13 715788 14 262771 15 615302 16 1457 17 650381 18 542652 19 101993 20 197937 21 474452 22 859631 23 327526 24 705522 25 500710 26 595050 27 577264 28 955258 29 269967 30 4012 31 471435...
output:
683940 335116 533478 562303 1187697 1501897 1772550 1834179 2485176 3178215 3337792 3804500 4520288 4783059 5398361 5399818 6050199 6592851 6694844 6892781 7367233 8226864 8554390 9259912 9760622 10355672 10932936 11888194 12158161 12162173 12633608 13385421 13746582 14637654 14649654 15558759 15771...
result:
ok 250000 numbers
Test #5:
score: 0
Accepted
time: 2514ms
memory: 63012kb
input:
99998 1 479670338308 2 121499701200 3 858712975908 4 144714509693 5 285977224040 6 864876191776 7 68574926716 8 310308615852 9 502806496434 10 361482163495 11 765497528076 12 895859015474 13 334706003457 14 379981526252 15 36757813515 16 157157422672 17 349512227463 18 338990361716 19 163391039440 2...
output:
479670338308 601170039508 1459883015416 1604597525109 1890574749149 2755450940925 2824025867641 3134334483493 3637140979927 3998623143422 4764120671498 5659979686972 5994685690429 6374667216681 6411425030196 6568582452868 6918094680331 7257085042047 7420476081487 7622906189099 8454399662437 89043817...
result:
ok 250000 numbers
Test #6:
score: 0
Accepted
time: 2518ms
memory: 63300kb
input:
99998 1 178045123943 2 547685852175 3 121241296998 4 254770970696 5 492051406869 6 202334193904 7 510144241379 8 319988611700 9 116337235366 10 879642794656 11 685411730399 12 350924727333 13 594085342571 14 548936135915 15 208962464142 16 862456709774 17 288075015418 18 829298359525 19 618337059019...
output:
178045123943 725730976118 846972273116 1101743243812 1593794650681 1796128844585 2306273085964 2626261697664 2742598933030 3622241727686 4307653458085 4658578185418 5252663527989 5801599663904 6010562128046 6873018837820 7161093853238 7990392212763 8608729271782 9144448114015 9555400007353 973058283...
result:
ok 250000 numbers
Test #7:
score: -100
Wrong Answer
time: 2502ms
memory: 63752kb
input:
99998 1 505218 1 389104 3 722814 4 114842 5 630847 6 266652 7 69086 8 188782 9 302082 10 791859 11 868547 12 207649 13 144886 14 249343 15 348080 16 430422 17 677611 18 246267 19 45035 20 530145 21 674630 22 619198 23 586278 24 546781 25 135381 26 191829 27 974891 28 296123 29 309858 30 867733 31 57...
output:
181131381 195039013 295916860 222197252 190593371 146829716 134057958 291368595 251363372 200021187 293925831 200698275 193084513 80189366 308086109 123556908 220108246 171669491 222301552 153106016 200985006 255624914 230587135 301029279 147951641 127525962 157093651 291414258 313601850 103238880 2...
result:
wrong answer 1st numbers differ - expected: '49938777', found: '181131381'