QOJ.ac

QOJ

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

Judging History

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

  • [2024-01-05 11:31:02]
  • 评测
  • 测评结果:0
  • 用时:819ms
  • 内存:172360kb
  • [2024-01-05 11:31:01]
  • 提交

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*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: 27296kb

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: 0ms
memory: 27248kb

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: 36ms
memory: 47036kb

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: 819ms
memory: 172360kb

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%