QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107382 | #6101. Ring Road | bulijiojiodibuliduo# | RE | 1037ms | 263844kb | C++ | 3.7kb | 2023-05-21 04:12:38 | 2023-05-21 04:12:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=201000;
const int M=401000;
const int L=35;
typedef pair<ll,int> PLI;
int n,m,T;
vector<array<ll,3>> E[N],e[N];
PII pe[M],comp[N][L];
VI rt[N*5];
ll dis[N][L][3];
int ss[N],col[N],del[N];
namespace dijk{
ll dis[N];
int vis[N];
priority_queue<PLI,vector<PLI>,greater<PLI>> hs;
const ll inf=1ll<<60;
void solve(int S,VI vtot) {
for (auto x:vtot) dis[x]=inf,vis[x]=0;
dis[S]=0;
hs.push(mp(dis[S],S));
while (!hs.empty()) {
int u=hs.top().se; hs.pop();
if (vis[u]) continue;
vis[u]=1;
for (auto [v,w,id]:E[u]) if (!del[id]) {
if (dis[v]>dis[u]+w) {
dis[v]=dis[u]+w;
hs.push(mp(dis[v],v));
}
}
}
}
}
void solve(int u,int sz,int lev) {
//printf("? %d %d %d\n",u,sz,lev);
if (sz==1) return;
int ms=sz+1,me=-1;
++T;
function<void(int,int)> dfs1=[&](int u,int par) {
ss[u]=1;
for (auto [v,w,id]:e[u]) {
if (v==par) continue;
if (del[id]) continue;
dfs1(v,u);
ss[u]+=ss[v];
int msz=max(ss[v],sz-ss[v]);
if (msz<ms) ms=msz,me=id;
}
};
VI re;
dfs1(u,-1);
assert(me!=-1);
//printf("me %d\n",me);
auto [pu,pv]=pe[me];
VI vu,vv,vtot;
int cc=1;
function<void(int,int)> dfs2=[&](int u,int par) {
vu.pb(u);
vtot.pb(u);
col[u]=cc;
comp[u][lev]=mp(T,cc);
for (auto [v,w,id]:e[u]) {
if (v==par) continue;
if (del[id]) continue;
dfs2(v,u);
}
};
dfs2(pv,pu); vv=vu; vu.clear();
cc=0; dfs2(pu,pv);
for (auto u:vu) for(auto [v,w,id]:E[u]) {
if (del[id]) continue;
assert(comp[v][lev].fi==T);
if (col[v]!=col[u]) {
re.pb(id);
//printf("dd %d %d %d\n",id,u,v);
}
}
set<int> tt;
for (auto x:re) tt.insert(pe[x].fi);
rt[T]=VI(all(tt));
int pc=0;
for (auto x:rt[T]) {
dijk::solve(x,vtot);
for (auto y:vtot) dis[y][lev][pc]=dijk::dis[y];
++pc;
}
for (auto x:re) {
//printf("del %d\n",x);
del[x]=1;
}
solve(pu,SZ(vu),lev+1);
solve(pv,SZ(vv),lev+1);
}
int eid,nn,p[N];
VI son[N];
ll c[N];
void add(int x,int y,ll w) {
++eid;
e[x].pb({y,w,eid});
e[y].pb({x,w,eid});
E[x].pb({y,w,eid});
E[y].pb({x,w,eid});
pe[eid]=mp(x,y);
}
int main() {
scanf("%d",&n);
rep(i,2,n+1) {
scanf("%d%lld",&p[i],&c[i]);
son[p[i]].pb(i);
}
int nn=n;
rep(i,1,n+1) {
int ps=i;
rep(j,0,SZ(son[i])) {
int v=son[i][j];
add(ps,v,c[v]);
if (j!=SZ(son[i])-1) {
add(ps,++nn,0);
ps=nn;
}
}
}
VI lef;
rep(i,1,n+1) if (son[i].empty()) {
lef.pb(i);
}
rep(i,0,SZ(lef)) {
ll v;
scanf("%lld",&v);
int x=lef[i],y=lef[(i+1)%SZ(lef)];
++eid;
pe[eid]=mp(x,y);
E[x].pb({y,v,eid});
E[y].pb({x,v,eid});
}
//rep(i,1,eid+1) printf("edges %d %d %d\n",i,pe[i].fi,pe[i].se);
solve(1,nn,0);
int q;
scanf("%d",&q);
rep(i,0,q) {
int x,y;
scanf("%d%d",&x,&y);
ll ans=1ll<<60;
int lev=0;
while (comp[x][lev].fi==comp[y][lev].fi&&comp[x][lev].fi!=0) {
int tt=comp[x][lev].fi;
rep(j,0,SZ(rt[tt])) ans=min(ans,dis[x][lev][j]+dis[y][lev][j]);
++lev;
}
printf("%lld\n",ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 41592kb
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: 4ms
memory: 42996kb
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: 7ms
memory: 41376kb
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: 493ms
memory: 175652kb
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: 495ms
memory: 176420kb
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: 486ms
memory: 175932kb
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: 489ms
memory: 177540kb
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: 498ms
memory: 177176kb
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: 0
Accepted
time: 515ms
memory: 175828kb
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:
ok 250000 numbers
Test #10:
score: 0
Accepted
time: 302ms
memory: 186288kb
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 #11:
score: 0
Accepted
time: 350ms
memory: 184820kb
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 #12:
score: 0
Accepted
time: 314ms
memory: 185412kb
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 #13:
score: 0
Accepted
time: 336ms
memory: 184876kb
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:
6475170685 18296468463 1121070836 16695742237 11066057805 42860720422 14428963674 3692054807 2227905259 1714915356 19131106974 9821315836 12524695522 3986823337 12790940916 22550803631 23610015238 3102309150 3401015881 18699384553 19905329907 865332423 6891760386 16835591504 6639521092 3148140627 17...
result:
ok 250000 numbers
Test #14:
score: 0
Accepted
time: 356ms
memory: 184708kb
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:
12203046887784113 10365327549230162 17079574516460217 4141534192921317 5429075254318531 3565765544700762 16952829218113345 5845875140946204 3890107933592949 984518580017239 17330516641751964 3699529649452223 11918426897241532 15952581467530069 3843116124947454 5370054179772823 16090340337819991 1375...
result:
ok 250000 numbers
Test #15:
score: 0
Accepted
time: 367ms
memory: 184716kb
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:
10339105026613567 14461690199915115 12690823238458067 7821178705209607 7076184629969823 16899171856091454 19437242126164987 11158951829491146 13679133170357567 15385713272973363 11365708278139910 1438468654825004 8861073082935820 4940900936389092 16614700449067911 13114868036582086 5311028510915450 ...
result:
ok 250000 numbers
Test #16:
score: 0
Accepted
time: 1037ms
memory: 263844kb
input:
99998 1 970533 1 240729 1 506011 4 913306 5 445101 5 366094 7 651162 8 863644 9 186883 10 233942 11 86762 12 214346 13 19463 14 9614 15 404874 16 919416 17 885137 17 158745 19 39820 19 881835 19 772416 22 797601 23 534988 23 74531 23 759376 26 541958 26 756133 28 265896 28 44502 30 79268 31 659653 3...
output:
970533 240729 506011 1419317 1864418 1785411 2436573 3300217 3487100 3721042 3807804 4022150 4041613 4051227 4456101 5375517 6260654 5534262 5574082 6416097 6306678 7104279 7639267 7178810 7863655 8405613 8619788 8885684 8664290 8743558 9403211 9600362 10335969 11073373 11794671 12403718 11850222 11...
result:
ok 250000 numbers
Test #17:
score: -100
Dangerous Syscalls
input:
99998 1 131124635252 1 936656049863 1 138174759305 4 966891691524 5 760667907438 6 289636283597 6 10442334563 6 497444176424 9 988258248677 10 831323449001 10 166319695829 12 86883156682 12 644172526728 14 657987082235 15 240058525125 16 856801349887 16 793474065491 16 838458499696 19 414532890647 2...