QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107382#6101. Ring Roadbulijiojiodibuliduo#RE 1037ms263844kbC++3.7kb2023-05-21 04:12:382023-05-21 04:12:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 04:12:41]
  • 评测
  • 测评结果:RE
  • 用时:1037ms
  • 内存:263844kb
  • [2023-05-21 04:12:38]
  • 提交

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...

output:


result: