QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88717#5828. 游戏Appleblue1780 942ms76484kbC++143.4kb2023-03-16 21:54:022023-03-16 21:54:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-16 21:54:02]
  • 评测
  • 测评结果:80
  • 用时:942ms
  • 内存:76484kb
  • [2023-03-16 21:54:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,q,ans[N];
vector <int> G[N];

struct dat{
	int dis,u,typ;
};
int dep[N],fx[N][20];
dat mx[N],mx2[N],mx3[N];

void upd(int u,dat V){
	if(V.dis>mx[u].dis) mx3[u]=mx2[u],mx2[u]=mx[u],mx[u]=V;
	else if(V.dis>mx2[u].dis) mx3[u]=mx2[u],mx2[u]=V;
	else if(V.dis>mx3[u].dis) mx3[u]=V;
}
void dfs(int u,int fa){
	fx[u][0]=fa;
	for(int t=1;t<=18;t++) fx[u][t]=fx[fx[u][t-1]][t-1];
	
	dep[u]=dep[fa]+1;
	mx[u]=mx2[u]=mx3[u]={0,u,0};
	for(int v: G[u]){
		if(v==fa) continue;
		dfs(v,u);
		upd(u,(dat){mx[v].dis+1,mx[v].u,0});
	}
}
void dfss(int u,int fa){
	for(int v: G[u]){
		if(v==fa) continue;
		if(mx[u].u!=mx[v].u) upd(v,(dat){mx[u].dis+1,mx[u].u,1});
		else upd(v,(dat){mx2[u].dis+1,mx2[u].u,1});
		dfss(v,u);
	}
}


inline int cal(int x,int y){
	return (x && y)?x:(x | y);
}
struct abc{
	int typ,a,b,c,num,pos;
}p[N*2];
int id;
bool cmp1(abc X,abc Y){
	if(X.a==Y.a) return X.typ<Y.typ;
	return X.a>Y.a;
}
bool cmp2(abc X,abc Y){
	if(X.b==Y.b) return X.typ<Y.typ;
	return X.b>Y.b;
}

int c[N];
inline int lowbit(int x){
	return x & (-x);
}
inline void modify(int x,int k){
	x++;
	while(x) c[x]=cal(c[x],k),x-=lowbit(x);
}
inline void clr(int x){
	x++;
	while(x) c[x]=0,x-=lowbit(x);
}
inline int query(int x){
	x++;
	int tot=0;
	while(x<=n+1) tot=cal(tot,c[x]),x+=lowbit(x);
	return tot;
}

void CDQ(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	
	sort(p+l,p+r+1,cmp2);
	for(int i=l;i<=r;i++){
		if(p[i].typ==1 && p[i].pos<=mid){
			modify(p[i].c,p[i].num);
		}
		else if(p[i].typ==2 && p[i].pos>mid && !ans[p[i].num]){
			ans[p[i].num]=cal(ans[p[i].num],query(p[i].c));
		}
	}
	for(int i=l;i<=r;i++)
		if(p[i].typ==1 && p[i].pos<=mid)
			clr(p[i].c);
}


int glca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int t=18;t>=0;t--)
		if(dep[fx[x][t]]>=dep[y]) x=fx[x][t];
	if(x==y) return x;
	for(int t=18;t>=0;t--)
		if(fx[x][t]!=fx[y][t]) x=fx[x][t],y=fx[y][t];
	return fx[x][0];
}
int kthfa(int x,int k){
	for(int t=20;t>=0;t--)
		if(k>=(1<<t)) x=fx[x][t],k-=1<<t;
	return x;
}
int getans(int u,dat V,int dis){
	if(!V.typ){
		return kthfa(V.u,V.dis-dis);
	}
	else{
		int lc=glca(u,V.u);
		if(dis<=dep[u]-dep[lc]){
			return kthfa(u,dis);
		}
		else{
			return kthfa(V.u,V.dis-dis);
		}
	}
}

int sav[N][3],P[N][3];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v; cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dep[0]=-1;
	dfs(1,0);
	dfss(1,0);
	for(int i=1;i<=n;i++){
		p[++id]={1,mx3[i].dis,mx2[i].dis,mx[i].dis,i};
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y,z; cin>>x>>y>>z;
		int a=(x+y-z)/2,b=(x+z-y)/2,c=(y+z-x)/2;
		sav[i][0]=a,sav[i][1]=b,sav[i][2]=c;
		P[i][0]=0,P[i][1]=1,P[i][2]=2;
		for(int t=1;t<=3;t++){
			if(a>b) swap(a,b),swap(P[i][0],P[i][1]);
			if(b>c) swap(b,c),swap(P[i][1],P[i][2]);
		}
		p[++id]={2,a,b,c,i};
	}
	
	sort(p+1,p+id+1,cmp1);
	for(int i=1;i<=id;i++) p[i].pos=i;
	CDQ(1,id);
	
	for(int i=1;i<=q;i++){
		int x=ans[i];
		dat V[3];
		for(int t=0;t<3;t++){
			if(P[i][0]==t) V[t]=mx3[x];
			if(P[i][1]==t) V[t]=mx2[x];
			if(P[i][2]==t) V[t]=mx[x];
		}
		
		int A=getans(x,V[0],sav[i][0]);
		int B=getans(x,V[1],sav[i][1]);
		int C=getans(x,V[2],sav[i][2]);
		cout<<A<<" "<<B<<" "<<C<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 3ms
memory: 12996kb

input:

500
279 196
182 105
400 14
278 217
198 411
379 318
120 421
314 95
437 325
23 433
71 485
192 154
90 224
180 71
328 93
183 101
404 349
223 285
492 100
366 480
29 328
200 448
365 156
226 231
129 167
246 273
171 452
284 6
131 471
229 90
480 48
448 157
240 221
7 36
401 200
255 438
436 110
281 489
388 258...

output:

125 285 94
346 488 386
478 342 285
193 215 149
144 350 360
53 436 17
146 480 6
440 311 451
239 144 342
150 4 230
306 497 356
487 217 456
452 436 361
423 248 328
17 333 285
497 48 356
453 343 328
496 247 211
353 349 270
314 401 114
245 360 177
211 353 406
478 454 80
429 416 50
305 215 406
436 386 346...

result:

ok Accepted!

Test #2:

score: 10
Accepted
time: 14ms
memory: 13280kb

input:

2000
643 1871
689 23
1822 1443
1031 1027
1655 845
189 771
1561 498
19 1778
576 1080
904 717
1690 291
1387 1077
398 811
1310 1231
645 1291
480 927
330 170
1464 1057
1033 894
1308 288
1292 1529
1212 122
1108 401
89 1118
1058 1088
1764 1314
981 1255
1893 864
180 1887
1903 843
734 1412
883 1013
1739 124...

output:

474 1244 1024
44 706 990
1565 1244 1630
1090 1159 1244
134 1840 1973
337 690 1779
798 1262 1738
668 1551 1878
1440 158 200
1533 1454 1028
264 1277 1147
1495 261 1201
1118 1208 1217
1978 31 1277
529 31 1752
1478 1402 1861
1277 1973 1840
515 166 1689
1472 1026 989
1254 307 368
1840 468 523
1081 945 10...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 514ms
memory: 47652kb

input:

200000
56968 132021
105656 107536
123627 58349
119191 138198
133708 142638
114350 24980
137784 40346
124158 130204
80684 183207
78156 94449
21893 157560
54464 73571
145830 57756
160288 32120
178632 142663
26565 185985
70576 24906
32217 115826
185756 137673
54280 179613
77826 144447
66005 29955
11745...

output:

161686 50151 60815

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 516ms
memory: 47536kb

input:

200000
41999 100683
85781 129266
122431 179332
162416 44814
24405 42267
154161 12483
178049 159964
67625 152391
133072 25866
178005 14695
94384 170290
54701 40323
66280 128515
159022 55057
14985 12920
182805 40659
173117 67973
99771 26102
198919 94543
23608 187601
61125 5759
89437 47647
18142 192402...

output:

21138 148400 122968

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 525ms
memory: 47744kb

input:

200000
195072 75458
31991 127114
60943 49502
186375 1130
45394 147217
168455 84307
132752 188952
101108 130004
107490 22003
16275 187645
111002 42669
138880 137115
112688 172751
81697 99037
166996 18495
2234 56119
170807 101349
105736 23180
148159 40863
136678 11849
190707 91245
61779 120740
157115 ...

output:

184458 188598 125785
163541 56238 186273
113081 39012 13235
26861 106144 160945
16658 157350 192448
8412 35694 91454
175168 88621 54064
48815 134805 37526
158076 81154 121210
91162 43513 13269

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 526ms
memory: 47552kb

input:

200000
48556 78408
155026 9376
8983 61211
150393 85068
90892 109283
75746 89742
6760 187245
168658 130735
68602 127646
60802 149828
22898 59471
172845 100274
42303 190696
7612 134905
94702 59800
129633 192496
19903 64869
51318 63358
34692 66030
98535 176606
153647 177529
157903 147292
106273 107278
...

output:

46013 89402 196644
165333 31595 87543
196600 44966 16436
40657 108839 54522
112974 104457 146338
6011 104277 89585
85385 22715 66829
59562 87964 193634
79717 84041 125351
26594 44088 33136

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 942ms
memory: 76484kb

input:

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

output:

17305 162949 100001
129804 100001 61045
5222 120705 100001
100001 79890 116671
64026 105656 100001
13516 100001 128131
100001 156172 41388
177629 100001 5761
25711 200000 68037
175188 154225 1
57460 60359 200000
39640 100001 121712
104028 83446 100001
6718 100001 183956
8968 108150 100001
17865 1000...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 857ms
memory: 57712kb

input:

200000
5732 55198
128966 25317
114737 116391
150003 18274
43867 70745
76222 4169
55976 114951
198396 72896
38647 19711
12756 172119
73197 117994
117512 14177
130965 126990
119440 183341
142023 60829
111893 57350
122754 123305
36525 79077
36447 91967
135405 170456
165839 147481
66074 175822
22238 264...

output:

56980 56980 144555
56980 56980 25686
36778 36778 178310
56980 56980 94149
56980 56980 38289
56980 56980 74592
56980 56980 5147
56980 56980 42452
56980 56980 197563
56980 56980 70042
56980 56980 45450
56980 56980 154727
56980 56980 143662
56980 56980 101637
56980 56980 20344
113946 113946 178310
5698...

result:

ok Accepted!

Test #9:

score: 0
Time Limit Exceeded

input:

200000
185063 17064
180987 114492
88071 71803
158363 135918
60910 54848
97338 6734
192937 9410
49617 199068
82499 63554
188791 188152
178767 40866
11304 27212
144234 138097
42236 3946
103355 12683
50992 20598
145723 48620
11709 115688
123172 121379
70541 130844
147827 39431
139372 61280
42705 54015
...

output:

91209 91828 54836
122282 37725 190275
120030 165504 81583
154175 153528 59038
158254 56702 91361
63905 58984 77065
121326 72487 133533
43623 21411 79690
155825 21012 67566
94623 191109 127302
116351 151586 162356
155985 164569 53591
24962 10321 195976
3649 83124 20602
82777 170043 41684
167969 18246...

result:


Test #10:

score: 0
Time Limit Exceeded

input:

200000
197244 185999
18639 124754
154223 12099
53676 167616
22710 22294
150412 66132
19320 75478
170410 122661
130961 175554
171586 85572
188386 81238
120249 117687
43214 126266
8744 165654
164725 189519
124144 170329
86605 100197
130545 17030
113301 96665
67733 187286
37846 146399
75352 117550
3235...

output:

50733 180014 183930
187358 17063 150075
54484 149425 21861
155162 125797 46700
175261 120909 108028
42644 139608 26522
43979 143540 198075
87366 56051 74697
92188 197397 5241
31435 72709 166942
55109 51709 149537
17330 72374 180261
144627 54081 156253
123951 114221 18321
169317 68603 67160
88879 167...

result: