QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297815#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》Kevin530715 1271ms254052kbC++204.0kb2024-01-05 11:20:572024-01-05 11:20:57

Judging History

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

  • [2024-01-05 11:20:57]
  • 评测
  • 测评结果:15
  • 用时:1271ms
  • 内存:254052kb
  • [2024-01-05 11:20:57]
  • 提交

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);
}
int lca(int u,int v)
{
	for(int i=19;i>=0;i--)
	{
		if(depth[anc[i][u]]>=depth[v])
			u=anc[i][u];
		if(depth[anc[i][v]]>=depth[u])
			v=anc[i][v];
	}
	if(u==v) return u;
	for(int i=19;i>=0;i--)
		if(anc[i][u]!=anc[i][v])
		{
			u=anc[i][u];
			v=anc[i][v];
		}
	return anc[0][u];
}
bool check(int u,int v)
{
	int d=depth[u]-depth[v];
	if(d<0) return false;
	for(int i=0;i<20;i++)
		if(d>>i&1)
			u=anc[i][u];
	return u==v;
}
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];
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			anc[i][j]=anc[i-1][anc[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*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: 0ms
memory: 120612kb

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: -5
Wrong Answer
time: 10ms
memory: 120344kb

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:

288230376151711744

result:

wrong answer 1st numbers differ - expected: '288230376151711752', found: '288230376151711744'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 32ms
memory: 147964kb

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: 15
Accepted

Test #45:

score: 15
Accepted
time: 1271ms
memory: 253380kb

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:

4
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
8
0
0
0
0
16
0
0
4096
0
0
0
0
4096
0
0
0
0
2
0
0
0
0
4
0
0
0
0
32
64
0
0
0
512
64
4
4096
0
2
0
0
131072
0
0
0
0
0
0
0
0
2
0
0
0
2
0
4096
2
0
0
0
0
0
512
2
8
0
0
4096
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
512
0
0
36
0
0
0
0
0
0
0
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 99210 numbers

Test #46:

score: 0
Accepted
time: 1229ms
memory: 254052kb

input:

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

output:

0
0
4096
2
0
0
8
0
0
16
0
0
0
0
0
128
0
532
2
640
0
16384
514
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
2
0
0
2
0
128
0
0
0
2
0
0
2
0
128
0
0
0
0
132
2
0
0
0
0
128
0
4
0
0
0
0
0
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
0
0
0
0
0
0
0
0
128
0
256
0
0
0
0
0
0
0
0
16
2
0
2
0
0
0
264
0
0
0
0
0
0
0
0
0
2
0
0
4
5...

result:

ok 99668 numbers

Test #47:

score: 0
Accepted
time: 1267ms
memory: 253536kb

input:

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

output:

0
0
0
0
2
0
0
0
2
0
0
0
0
0
0
0
0
1024
0
0
0
256
0
2
0
0
131104
0
0
131104
2
0
1024
0
0
0
258
0
0
16388
0
0
0
256
0
0
0
0
2
2
0
32
0
0
0
16384
0
0
32
4
0
0
2
0
0
0
2
0
0
1026
8
0
8
4
0
4
2
0
0
0
0
0
1024
0
2
0
36
0
2
0
4
0
32
0
2
2
0
8192
0
0
0
0
0
0
0
4098
0
0
0
0
0
32
4098
1024
0
2
2
0
0
0
4
4096
...

result:

ok 99396 numbers

Test #48:

score: 0
Accepted
time: 1229ms
memory: 253500kb

input:

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

output:

0
0
0
0
0
0
4
0
4096
1024
0
4
0
16
64
8
0
0
0
0
1024
0
0
0
0
256
0
0
0
0
8192
0
0
1028
0
4
4
0
0
0
0
0
0
0
1024
0
0
0
16
0
0
2
0
0
0
0
0
0
0
4
0
64
4
0
524288
0
0
0
36
0
0
0
0
0
0
0
0
0
0
0
4096
1024
0
0
0
0
0
2
0
0
8
0
16
0
0
0
96
64
64
0
0
0
2
64
0
0
66
0
2
0
4096
0
0
0
2
64
0
0
0
0
2
0
0
256
0
0
...

result:

ok 99733 numbers

Subtask #8:

score: 0
Skipped

Dependency #1:

0%