QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297818#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》Kevin53070 646ms175548kbC++203.5kb2024-01-05 11:27:342024-01-05 11:27:34

Judging History

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

  • [2024-01-05 11:27:34]
  • 评测
  • 测评结果:0
  • 用时:646ms
  • 内存:175548kb
  • [2024-01-05 11:27:34]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[1001000];
int n;
ll a[1001000];
int depth[1001000];
int anc[20][1001000];
int mx[20][1001000];
int dfn[1001000],son[1001000],siz[1001000],tp[1001000],tot;
void dfs1(int u,int fa)
{
	siz[u]=1;
	depth[u]=depth[fa]+1;
//	anc[0][u]=fa;
//	mx[0][u]=a[u];
	for(auto v:G[u])
		if(v!=fa)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])
				son[u]=v;
		}
}
void dfs2(int u,int fa)
{
	if(!tp[u]) tp[u]=u;
	dfn[u]=++tot;
	if(son[u])
	{
		tp[son[u]]=tp[u];
		dfs2(son[u],u);
	}
	for(auto v:G[u])
		if(v!=son[u]&&v!=fa)
			dfs2(v,u);
}
ll b[1001000];
int range_max(int l,int r)
{
	int x=__lg(r-l+1);
	return (b[mx[x][l]]>b[mx[x][r-(1<<x)+1]])?mx[x][l]:mx[x][r-(1<<x)+1];
}
struct _comp_{const bool operator ()(const array<int,3> &a,const array<int,3> &b){return ::b[a[0]]>::b[b[0]];}};
#define count _count
int cnt[1001000],count;
int trans[1001000][2];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)
		b[dfn[i]]=a[i];
	for(int i=1;i<=n;i++)
		mx[0][i]=i;
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			if(j+(1<<(i-1))<=n)
				mx[i][j]=(b[mx[i-1][j]]>b[mx[i-1][j+(1<<(i-1))]])?mx[i-1][j]:mx[i-1][j+(1<<(i-1))];
			else
				mx[i][j]=mx[i-1][j];
	int q;
	cin>>q;
	ll lstans=0;
	while(q--)
	{
		int u,v,m;
		ll a,b;
		cin>>a>>b>>m;
		u=(a^lstans)%n+1;
		v=(b^lstans)%n+1;
		priority_queue<array<int,3>,vector<array<int,3>>,_comp_> pq;
		while(tp[u]!=tp[v])
		{
			if(depth[tp[u]]<depth[tp[v]]) swap(u,v);
			pq.push({range_max(dfn[tp[u]],dfn[u]),dfn[tp[u]],dfn[u]});
			u=anc[0][tp[u]];
		}
		if(dfn[u]>dfn[v]) swap(u,v);
		pq.push({range_max(dfn[u],dfn[v]),dfn[u],dfn[v]});
		vector<ll> vec;
		while(sz(vec)<(m+1)*64&&!pq.empty())
		{
			array<int,3> arr=pq.top();
			pq.pop();
			vec.pb(::b[arr[0]]);
			if(arr[0]!=arr[1])
				pq.push({range_max(arr[1],arr[0]-1),arr[1],arr[0]-1});
			if(arr[0]!=arr[2])
				pq.push({range_max(arr[0]+1,arr[2]),arr[0]+1,arr[2]});
		}
		count=1;
		for(auto val:vec)
		{
			int cur=1;
			cnt[cur]++;
			for(int i=61;i>=0;i--)
			{
				int c=val>>i&1;
				if(!trans[cur][c]) trans[cur][c]=++count;
				cur=trans[cur][c];
				cnt[cur]++;
			}
		}
		vector<int> cn;
		ll ans=0;
		cn.pb(1);
		for(int i=61;i>=0;i--)
		{
			int sum=0;
			for(auto nd:cn)
				sum+=cnt[trans[nd][1]];
			vector<int> ncn;
			for(auto nd:cn)
				if(trans[nd][1])
					ncn.pb(trans[nd][1]);
			if(sum<m)
			{
				for(auto nd:cn)
					if(trans[nd][0])
						ncn.pb(trans[nd][0]);
			}
			else
				ans|=(1ll<<i);
			swap(cn,ncn);
		}
		for(int i=1;i<=count;i++)
			cnt[i]=trans[i][0]=trans[i][1]=0;
		cout<<(lstans=ans)<<'\n';
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 3ms
memory: 79652kb

input:

931
184 700
485 184
419 485
386 419
308 386
114 308
301 114
598 301
120 598
144 120
595 144
812 595
236 812
7 236
543 7
327 543
858 327
68 858
177 68
398 177
899 398
408 899
848 408
202 848
269 202
304 269
540 304
647 540
672 647
314 672
157 314
241 157
745 241
300 745
343 300
92 343
117 92
30 117
2...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #2:

score: 0
Accepted
time: 0ms
memory: 79896kb

input:

915
911 748
514 911
805 514
729 805
753 729
40 753
671 40
664 671
94 664
61 94
726 61
690 726
597 690
216 597
644 216
533 644
605 533
22 605
307 22
455 307
377 455
114 377
660 114
589 660
569 589
409 569
408 409
821 408
736 821
599 736
60 599
475 60
57 475
412 57
85 412
524 85
846 524
595 846
262 59...

output:

288230376151711752

result:

ok 1 number(s): "288230376151711752"

Test #3:

score: 0
Accepted
time: 8ms
memory: 81728kb

input:

930
111 896
637 111
559 637
289 559
103 289
759 103
341 759
605 341
778 605
154 778
169 154
721 169
631 721
741 631
750 741
344 750
641 344
639 641
769 639
48 769
389 48
25 389
70 25
508 70
185 508
199 185
602 199
89 602
473 89
565 473
373 565
865 373
867 865
658 867
271 658
685 271
269 685
317 269
...

output:

268435456

result:

ok 1 number(s): "268435456"

Test #4:

score: 0
Accepted
time: 3ms
memory: 79684kb

input:

948
537 716
933 537
605 933
563 605
801 563
860 801
19 860
717 19
908 717
820 908
885 820
693 885
69 693
263 69
129 263
295 129
880 295
303 880
12 303
299 12
1 299
421 1
312 421
720 312
100 720
438 100
380 438
386 380
223 386
627 223
293 627
387 293
709 387
193 709
640 193
906 640
34 906
405 34
790 ...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #5:

score: 0
Accepted
time: 3ms
memory: 78812kb

input:

928
626 381
247 626
97 247
358 97
886 358
898 886
736 898
776 736
75 776
123 75
512 123
223 512
355 223
530 355
95 530
523 95
903 523
144 903
324 144
382 324
487 382
127 487
538 127
171 538
836 171
129 836
259 129
914 259
574 914
7 574
141 7
246 141
65 246
482 65
865 482
265 865
690 265
925 690
449 ...

output:

134217728

result:

ok 1 number(s): "134217728"

Test #6:

score: 0
Accepted
time: 4ms
memory: 79100kb

input:

941
87 448
396 87
398 396
623 398
837 623
234 837
896 234
258 896
700 258
52 700
27 52
515 27
308 515
774 308
76 774
21 76
753 21
493 753
902 493
878 902
58 878
146 58
342 146
414 342
312 414
621 312
88 621
460 88
683 460
150 683
845 150
535 845
467 535
326 467
247 326
280 247
474 280
124 474
22 124...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #7:

score: -5
Wrong Answer
time: 0ms
memory: 79384kb

input:

947
635 486
821 635
758 821
504 758
470 504
170 470
468 170
778 468
560 778
864 560
308 864
213 308
43 213
849 43
525 849
126 525
681 126
785 681
640 785
254 640
354 254
263 354
455 263
295 455
714 295
474 714
64 474
794 64
582 794
325 582
676 325
176 676
393 176
624 393
86 624
205 86
359 205
704 35...

output:

72057594037927936

result:

wrong answer 1st numbers differ - expected: '1152921504606846976', found: '72057594037927936'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 27ms
memory: 96524kb

input:

99115
98506 98914
1961 98506
45808 1961
23027 45808
16655 23027
66393 16655
77250 66393
68284 77250
53684 68284
21189 53684
84955 21189
73464 84955
47574 73464
40651 47574
21101 40651
6589 21101
59680 6589
6185 59680
25529 6185
207 25529
33286 207
98459 33286
92565 98459
85446 92565
97388 85446
1630...

output:

10

result:

wrong answer 1st numbers differ - expected: '2050', found: '10'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Wrong Answer

Test #45:

score: 0
Wrong Answer
time: 646ms
memory: 175548kb

input:

996678
2 1
3 1
4 1
5 1
6 3
7 5
8 5
9 5
10 7
11 8
12 9
13 1
14 2
15 7
16 4
17 5
18 17
19 16
20 2
21 1
22 1
23 9
24 17
25 19
26 10
27 9
28 7
29 25
30 25
31 4
32 11
33 31
34 21
35 13
36 19
37 25
38 10
39 11
40 20
41 35
42 1
43 19
44 20
45 41
46 1
47 19
48 5
49 28
50 21
51 33
52 7
53 14
54 21
55 20
56 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st numbers differ - expected: '4', found: '0'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%