QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218730 | #6101. Ring Road | 275307894a | WA | 403ms | 62256kb | C++14 | 2.6kb | 2023-10-18 17:42:58 | 2023-10-18 17:42:59 |
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);}
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>=0) 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: 100
Accepted
time: 0ms
memory: 40724kb
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: 40668kb
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: 6ms
memory: 40620kb
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: 260ms
memory: 60856kb
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: 278ms
memory: 61024kb
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: 300ms
memory: 60808kb
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: 0
Accepted
time: 380ms
memory: 62100kb
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:
49938777 183635999 291401080 222197252 152860291 146829716 117562120 288851477 115289410 138187501 289382499 200698275 193084513 80189366 308086109 123556908 220108246 57739237 205655324 153106016 175295026 56841964 226043803 301029279 147951641 127525962 157093651 291414258 313601850 102156566 2156...
result:
ok 250000 numbers
Test #8:
score: 0
Accepted
time: 403ms
memory: 62256kb
input:
99998 1 554852632074 1 877287935997 3 863063671260 4 807596967492 5 817277345167 6 963454496337 7 35181087309 8 682566158188 9 618067491408 10 163993674555 11 37973654749 12 544138262869 13 219011600890 14 444041187252 15 282634304121 16 793774000524 17 15450446700 18 355176887372 19 447528097591 20...
output:
36965622913940 32770119754145 120174886915036 175254080000187 62418986141396 175674957932261 180655959165950 102106066388664 29131554988904 34374587437849 122953102595140 55281766592353 107735923046596 88589612479211 92938994634909 172287081033431 70206151959994 112140581212107 150187289709607 12604...
result:
ok 250000 numbers
Test #9:
score: -100
Wrong Answer
time: 399ms
memory: 62012kb
input:
99998 1 337970157731 2 733936784289 3 38690932141 4 458709248187 5 438708156192 6 955898305396 7 252188236483 8 226770136460 9 784882978281 10 581223663945 11 571145073652 12 18757792382 13 437234520805 14 605539408269 15 176108201879 16 1136649828 17 952302049470 18 739298670877 19 79494920828 20 9...
output:
159859740372295 217564176871359 137919553934290 166298320003622 46637364653325 144112640342261 211279971651073 161285633950603 190697294613587 60084753950595 97315660610726 217340534406035 24636886425737 143715928829509 131318785395185 91650500710076 139107271184521 180819789153384 158577083125405 2...
result:
wrong answer 78th numbers differ - expected: '180430659260059', found: '185897517195327'