QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#516777#4401. Prizehotboy27030 1025ms203744kbC++142.8kb2024-08-12 21:29:162024-08-12 21:29:16

Judging History

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

  • [2024-08-12 21:29:16]
  • 评测
  • 测评结果:0
  • 用时:1025ms
  • 内存:203744kb
  • [2024-08-12 21:29:16]
  • 提交

answer

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))	
const ll MAXN = 5e5+100;
const ll MAXK = 19;
ll n,k,q,t;
struct tree{
	vector <ll> g[MAXN];
	ll depth[MAXN];
	ll sp[MAXN][MAXK];
	vector <pll> adj[MAXN];
	ll dp[MAXN];
	vector <ll> choose;
	ll in[MAXN],timeDFS;
	void dfs(ll u,ll p){
		sp[u][0] = p;
		in[u] = ++timeDFS;
		for (ll j = 1;j < MAXK;j ++){
			sp[u][j] = sp[sp[u][j-1]][j-1];
		}
		depth[u] = depth[p]+1;
		choose.push_back(u);
		for (auto v:g[u]){
			if (v==p)continue;
			dfs(v,u);
		}
	}
	ll lca(ll u,ll v){
		if (depth[u] > depth[v])swap(u,v);
		for (ll j = MAXK-1;j >= 0;j --){
			if (depth[sp[v][j]] >= depth[u])v = sp[v][j];
		}
		if (u==v)return u;
		for (ll j = MAXK-1;j >= 0;j--){
			if (sp[v][j] != sp[u][j])u = sp[u][j],v = sp[v][j];
		}
		return u;
	}
	ll root=-1;
	void add(ll u,ll v,ll wu,ll wv){
		ll LCA = lca(u,v);
		if (root==-1||depth[LCA]<depth[root])root=LCA;
		adj[LCA].push_back(MP(u,wu));
		adj[u].push_back(MP(LCA,wu));
		adj[LCA].push_back(MP(v,wv));
		adj[v].push_back(MP(LCA,wv));
	}
	void solve(){
		// for (ll i = 1;i <= n;i ++){
		// 	if (dp[i] == 0){
				queue <ll> q;
				q.push(root);
				while (!q.empty()){
					ll u = q.front();
					q.pop();
					for (auto [v,w]:adj[u]){
						if (v != u && dp[v] == 0){
							dp[v] = dp[u] + (depth[u] > depth[v] ? -1 : + 1) * w;
							q.push(v);
						}
					}
				}
			// }
		// }
	}
	ll query(ll u,ll v){
		ll LCA = lca(u,v);
		return dp[u] + dp[v] - dp[LCA]*2;
	}
} a1,a2;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n>>k>>q>>t;
	ll r1,r2;
	for (ll i = 1;i <= n;i ++){
		ll x;
		cin>>x;
		if (x!=-1){
			a1.g[x].push_back(i);
			a1.g[i].push_back(x);
		}
		else r1 = i;
	}
	// cout<<"OK"<<endl;
	for (ll i = 1;i <= n;i ++){

		ll x;
		cin>>x;
		if (x!=-1){
			a2.g[x].push_back(i);
			a2.g[i].push_back(x);
		}
		else r2 = i;
	}
	// cout<<"OK"<<endl;
	a1.dfs(r1,r1);
	a2.dfs(r2,r2);
	// cout<<"WAT"<<endl;
	// return 0;
	vector <ll> c = a2.choose;
	c.resize(k);
	sort(c.begin(),c.end(),[](ll x,ll y){return a1.in[x] < a1.in[y];});
	for (auto x:c)cout<<x<<' ';
	cout<<'\n';
	for (ll j = 0;j + 1 < sz(c);j ++)cout<<"? "<<c[j]<<' '<<c[j+1]<<'\n';
	cout<<'!'<<endl;
	for (ll j = 0;j + 1 < sz(c);j ++){
		ll u1,v1,u2,v2;
		cin>>u1>>v1>>u2>>v2;
		a1.add(c[j],c[j+1],u1,v1);
		a2.add(c[j],c[j+1],u2,v2);
	}
	// return 0;
	a1.solve(),a2.solve();
	// return 0;
	vector <pll> ans;
	while (t--){
		ll x,y;
		cin>>x>>y;
		ans.push_back(MP(a1.query(x,y),a2.query(x,y)));
		// cout<<a1.query(x,y)<<' '<<a2.query(x,y)<<'\n';
	}
	for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n';
	cout.flush();
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 885ms
memory: 201000kb

input:

500000 64682 64681 100000
46115
470589
209303
2979
473162
343535
79503
299539
404621
102085
237721
279170
392890
165201
441593
456314
218991
358478
86614
410800
159785
169761
95368
285837
297549
370283
378974
26449
444381
39320
149913
404523
144109
174828
263837
49847
468694
478535
152644
216598
301...

output:

422989 414496 290928 388223 160563 301045 470257 259625 222733 231286 345214 169817 435263 277447 386014 210139 455433 225855 264772 199736 355788 288506 233893 146148 454958 267562 498596 183745 352665 151125 266374 43142 9414 204593 212097 311775 25324 300764 6643 94847 396968 428563 311355 255767...

result:

ok good job!

Test #2:

score: 10
Accepted
time: 957ms
memory: 203360kb

input:

500000 90967 90966 100000
122547
312039
290084
118442
352297
175176
294396
496975
127062
90539
132654
408480
493670
419897
53432
141795
264165
60368
473480
5634
253119
64236
85346
422987
28583
262389
111931
271291
13577
415079
132797
256502
76402
265607
11274
289667
398726
32021
302401
410650
369760...

output:

3090 193269 3028 186608 498475 64618 82114 231445 7541 329983 134623 235591 70401 18906 403427 280451 146897 355174 160090 144279 193430 332022 488244 228900 80781 84465 218682 27818 6035 368489 155673 440755 443926 241570 193717 143661 374105 56616 323329 95909 337798 20531 236329 28564 437244 4969...

result:

ok good job!

Test #3:

score: 0
Wrong Answer
time: 724ms
memory: 183156kb

input:

500000 68287 68286 100000
273928
229768
65518
144983
311611
494773
489379
439644
467893
456131
430188
247387
485565
272285
474827
476962
338340
365804
344570
390867
390170
456217
43185
447057
385874
305750
107742
230530
259907
252254
280920
16831
45761
185191
117450
55891
175190
255615
35904
14855
2...

output:

242387 146602 106115 32426 8390 3821 314935 201979 171459 413397 469146 119187 74265 167902 479051 182695 260054 235048 135315 280891 13044 240704 209304 211564 188960 481631 289686 273785 175837 385737 204887 288861 330677 315423 120726 278204 129910 396267 322633 472675 325914 329277 67326 391455 ...

result:

wrong answer wrong answer on the first integer of query #1: read 12243 but expected 14620

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 25
Accepted
time: 1025ms
memory: 203744kb

input:

500000 88721 177440 100000
30974
23891
211201
125199
180489
387190
218020
498838
230147
307989
484136
257785
353027
304420
311738
169842
334090
486070
126212
328609
174959
368840
238722
418092
488389
226349
427271
457322
332454
12958
197530
264474
355717
482774
221286
282148
216441
266659
213750
628...

output:

63742 263216 146169 50728 199716 469441 459156 322328 152164 66876 274063 180006 237497 208598 249207 359435 96669 110070 41714 147909 214779 59127 151892 216797 194356 199621 20899 418742 198323 158340 163745 123748 85656 172672 123919 47108 313725 12227 183377 183933 348552 102798 184923 290145 17...

result:

ok good job!

Test #14:

score: 25
Accepted
time: 959ms
memory: 199956kb

input:

500000 50267 100532 100000
68723
142685
445548
215087
478634
201362
177405
373123
227456
161487
276716
452818
230715
466238
250886
368974
77152
493722
129115
154402
319190
170867
27898
338290
170229
428001
62611
19188
164329
435154
128
358453
137653
430592
160391
407392
125236
320137
27945
393135
17...

output:

154816 362396 450037 134811 7518 38422 119314 43275 412297 380046 465285 405991 75531 379813 36281 281211 137834 336400 10173 219815 389857 29366 476153 333693 222590 318117 4684 259586 214152 484414 225911 152245 481486 109527 42793 47295 294599 177444 430241 227553 353815 421724 89015 337781 46301...

result:

ok good job!

Test #15:

score: 0
Wrong Answer
time: 781ms
memory: 183108kb

input:

500000 67604 135206 100000
269046
235003
144646
314602
323547
204450
484229
26672
78499
602
110738
117079
125630
408912
188317
256853
71590
365703
370008
194267
342683
400737
369194
127912
96314
269751
219125
431887
398790
200053
279314
365797
187505
75025
48264
492515
387506
13267
80948
378737
1106...

output:

35015 347431 88597 414354 482857 397065 53183 354769 71664 51245 149001 236219 214693 499786 495321 413412 317633 211084 73492 227415 433440 9224 282936 375177 297475 150630 216010 319455 181652 118510 299772 383585 365737 274800 219207 372367 381196 467630 65752 287268 251434 60618 268518 195142 26...

result:

wrong answer wrong answer on the first integer of query #1: read 417002 but expected 13719

Subtask #3:

score: 0
Wrong Answer

Test #25:

score: 19
Accepted
time: 637ms
memory: 194060kb

input:

500000 200 199 40000
76296
130139
291501
292412
139543
433345
372726
451574
18315
465578
324564
477223
237354
81532
65170
465332
342130
9670
193303
193680
129668
149532
268907
89969
398275
356210
324593
433492
482232
466692
135343
433758
102545
287283
432859
351864
305769
489532
101532
450535
295762...

output:

464387 27779 146694 443858 405500 46371 375328 183696 253669 95388 173896 183797 18073 431275 140576 468877 345574 227090 361228 17134 261985 60381 64649 124883 275006 345205 205047 166559 173438 437370 498046 158980 365732 106698 145138 342120 407307 83109 296453 316074 219468 97176 251586 177490 2...

result:

ok good job!

Test #26:

score: 19
Accepted
time: 613ms
memory: 193852kb

input:

500000 200 199 40000
83785
150667
304961
267635
97760
385201
77226
6522
352645
72592
427133
30755
100574
359648
403948
394809
425453
115868
11287
351385
494434
245106
58157
395180
326236
277135
359592
13569
76251
45366
172378
122783
216597
466130
284420
342613
471698
380682
92490
79264
241049
54038
...

output:

332473 244705 329425 11670 1976 487833 9007 276165 332796 312780 40729 316303 262301 333879 107770 492625 290121 131493 452498 165311 58291 430151 17928 144890 413013 491676 82978 491900 220829 88480 488804 85566 226877 148451 471377 89209 413295 493138 228587 42773 455217 374293 451378 249388 39514...

result:

ok good job!

Test #27:

score: 0
Wrong Answer
time: 538ms
memory: 175204kb

input:

500000 200 199 40000
94863
498513
460682
411416
360517
309831
253717
325019
496632
255803
130770
289206
181204
74729
481723
293737
94126
307214
342974
448321
17084
433126
387809
279606
251781
65795
125269
129465
433572
219622
11806
179248
367117
84640
114067
122590
4140
116015
77759
392439
408930
10...

output:

169886 353970 165772 35671 120488 360404 48001 458381 167337 252993 223945 396664 121542 188473 370616 320801 171804 89934 69710 140435 365836 256733 210565 12566 194461 287204 297993 348301 241605 165284 95484 389971 390030 131636 396905 327597 255698 325220 289186 490101 313430 204679 28580 7557 2...

result:

wrong answer wrong answer on the first integer of query #2: read 12648 but expected 9313

Subtask #4:

score: 0
Runtime Error

Test #37:

score: 0
Runtime Error

input:

1000000 1000 999 100000
678746
439069
32542
85937
936926
284219
461661
203235
533462
940676
230275
621140
780674
254931
562355
229273
201341
493976
358955
963527
880412
91220
474599
160086
698841
591551
718276
844558
39859
765917
34722
401724
219774
443004
682244
545401
968419
968020
354030
411187
1...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%