QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90581#5828. 游戏Kanate10 615ms58096kbC++144.1kb2023-03-23 20:00:542023-03-23 20:00:56

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-23 20:00:56]
  • 评测
  • 测评结果:10
  • 用时:615ms
  • 内存:58096kb
  • [2023-03-23 20:00:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rint int
#define endl '\n'
int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return x*f;
}const int N=2e5+10,p=1e9;

int n,m;
vector<int> e[N];
struct Val{
	int x,id;
	bool operator <(const Val &A)const{return x>A.x;}
};
struct data{
	Val x,y,z;
	void operator+=(const Val &A)
	{
		if(A<x) z=y,y=x,x=A;
		else if(A<y) z=y,y=A;
		else if(A<z) z=A;
	}
}d[N];
void dfs(int x=1,int fa=1)
{
	d[x]={0,x,-p,0,-p,0};
	for(auto &it:e[x])
	if(it!=fa)
	{
		dfs(it,x);
		Val res=d[it].x;
		res.x++,d[x]+=res;
	}
}
Val sum[N],suf[N];
void sel(int x=1,int fa=1,Val res={-p,0})
{
	res.x++,d[x]+=res;
	int sz=e[x].size();Val tmp;
	for(rint i=0;i<sz;i++) tmp=d[e[x][i]].x,tmp.x++,sum[e[x][i]]=suf[e[x][i]]=(e[x][i]==fa?res:min(tmp,res));
	for(rint i=1;i<sz;i++)  sum[e[x][i]]=min(sum[e[x][i]],sum[e[x][i-1]]);
	for(rint i=sz-2;~i;i--) suf[e[x][i]]=min(suf[e[x][i]],suf[e[x][i+1]]);
	if(sz==1) return;
	if(e[x][0]!=fa)	   sel(e[x][0],x,suf[e[x][1]]);
	if(e[x][sz-1]!=fa) sel(e[x][sz-1],x,sum[e[x][sz-2]]);
	for(rint i=1;i+1<sz;i++)
	if(e[x][i]!=fa) sel(e[x][i],x,min(sum[e[x][i-1]],suf[e[x][i+1]]));
}

int mm;
struct node{
	int x,y,z,id,how;
}q[N];
struct cmp{
	bool operator ()(const node &A,const node &B){return A.z<B.z;}
};
bool cmpx(const node &A,const node &B){return A.x!=B.x?A.x<B.x:A.how>B.how;}
bool cmpy(const node &A,const node &B){return A.y!=B.y?A.y<B.y:A.how>B.how;}
multiset<node,cmp> s;
vector<node> ve[N];
bool use[N];
void cdq(int l=1,int r=mm)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	sort(q+l,q+mid+1,cmpy),sort(q+mid+1,q+r+1,cmpy);
	for(rint i=l,j=mid+1;j<=r;j++)
	{
		while(i<=mid&&q[i].y<=q[j].y){
			if(q[i].how&&!use[q[i].id]) s.insert(q[i]);
			i++;
		}
		if(!q[j].how)
		{
			auto it=s.upper_bound(q[j]);
			while(it!=s.begin())
			{
				--it;
				ve[q[j].id].push_back(*it),use[it->id]=1;
				it=s.erase(it);
			}
		}
	}
	s.clear();
	cdq(mid+1,r);
}

void init()
{
	dfs(),sel();
//	for(rint i=1;i<=n;i++) 
//		cout<<i<<":("<<d[i].x.x<<" "<<d[i].x.id<<") "
//		<<"("<<d[i].y.x<<" "<<d[i].y.id<<") "
//		<<"("<<d[i].z.x<<" "<<d[i].z.id<<")"<<endl;
	mm=m;
	for(rint i=1;i<=n;i++) q[++mm]={d[i].x.x,d[i].y.x,d[i].z.x,i,0};
	cdq();
//	for(rint i=1;i<=n;i++)
//	{
//		cout<<i<<": ";
//		for(auto &it:ve[i]) cout<<it.id<<" ";cout<<endl;
//	}
}

int FA[N],D[N],sz[N],son[N];
int dfn[N],tot,top[N],o[N];
void dfs1(int x=1,int fa=0,int dep=1)
{
	FA[x]=fa,D[x]=dep,sz[x]=1;
	for(auto &it:e[x])
	if(it!=fa)
	{
		dfs1(it,x,dep+1),sz[x]+=sz[it];
		if(sz[son[x]]<sz[it]) son[x]=it;
	}
}
void dfs2(int x=1,int tp=1)
{
	dfn[x]=++tot,top[x]=tp,o[tot]=x;
	if(!son[x]) return;
	dfs2(son[x],tp);
	for(auto &it:e[x])
	if(!dfn[it]) dfs2(it,it);
}

int ask(int l,int r,int dep)
{
	int x=l,y=r,fa;
	while(top[x]!=top[y])
	{
		if(D[top[x]]<D[top[y]]) swap(x,y);
		x=FA[top[x]];
	}
	if(D[x]>D[y]) fa=y;
	else fa=x;
//	cout<<"ask "<<l<<" "<<r<<" "<<fa<<" "<<dep<<endl;
	if(D[l]-dep>=D[fa])
	{
		int tar=D[l]-dep;
		while(D[top[l]]>tar) l=FA[top[l]];
		return o[dfn[l]-(D[l]-tar)];
	}
	else
	{
		int tar=D[fa]+dep-(D[l]-D[fa]);
		while(D[top[r]]>tar) r=FA[top[r]];
		return o[dfn[r]-(D[r]-tar)];
	}
}

struct ANS{
	int x,y,z;
}ans[N];

void work()
{
	dfs1(),dfs2();
	for(rint i=1;i<=n;i++)
	for(auto &it:ve[i])
		ans[it.id]={ask(i,d[i].x.id,it.x),ask(i,d[i].y.id,it.y),ask(i,d[i].z.id,it.z)};
	for(rint i=1;i<=m;i++) cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].z<<endl;
}

signed main()
{
//	ios::sync_with_stdio(0);
	n=read();
	for(rint i=1;i<n;i++)
	{
		int x=read(),y=read();
		e[x].push_back(y),e[y].push_back(x);
	}
	m=read();
	for(rint i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		q[i]={(x-y+z)>>1,(x+y-z)>>1,(y+z-x)>>1,i,1};
		if(q[i].y>q[i].x) swap(q[i].y,q[i].x);
		if(q[i].z>q[i].y) swap(q[i].z,q[i].y);
		if(q[i].y>q[i].x) swap(q[i].y,q[i].x);
//		cout<<"q "<<i<<" "<<q[i].x<<" "<<q[i].y<<" "<<q[i].z<<endl;
	}
	init();
	work();
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 12884kb

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:

37 344 21
312 386 488
125 362 21
215 193 149
330 386 297
165 26 280
28 193 486
283 360 261
30 399 268
151 60 87
152 360 427
270 74 183
227 124 265
342 399 124
17 146 21
477 360 427
331 60 477
266 60 417
39 74 323
360 17 219
281 26 438
10 298 331
68 399 332
205 50 416
152 152 331
270 356 51
37 172 18...

result:

wrong answer Wrong answer on test 1

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 13176kb

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:

1449 441 1560
0 0 0
679 275 650
1381 1941 1955
861 546 266
1937 926 234
0 0 0
87 552 731
1672 215 891
798 1546 396
861 1596 1215
1143 1671 1756
134 1060 589
822 182 422
1050 725 422
895 546 605
822 546 266
1981 552 951
0 0 0
0 0 0
1272 1772 266
1050 243 504
0 0 0
646 1726 1795
27 1557 323
1396 303 1...

result:

wrong answer Wrong answer on test 1

Test #3:

score: 0
Wrong Answer
time: 212ms
memory: 36508kb

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:

44708 71361 45838

result:

wrong answer Wrong answer on test 1

Test #4:

score: 10
Accepted
time: 213ms
memory: 36572kb

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:

154818 24899 74592

result:

ok Accepted!

Test #5:

score: 0
Wrong Answer
time: 222ms
memory: 36848kb

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:

137496 35530 1448
144255 179117 137984
53739 119043 89886
90290 141295 148920
156208 103697 171061
22907 153727 29198
40968 68885 112619
12553 23757 141497
93534 22362 21452
1480 63023 129015

result:

wrong answer Wrong answer on test 1

Test #6:

score: 0
Wrong Answer
time: 228ms
memory: 36556kb

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:

151532 107872 41374
59536 11082 166333
176954 191314 147915
53508 7072 78768
197721 25606 48857
164631 60403 28349
110232 16163 3
117163 99474 92047
188690 169825 168093
63864 46567 113102

result:

wrong answer Wrong answer on test 1

Test #7:

score: 0
Wrong Answer
time: 365ms
memory: 58096kb

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:

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 Integer 0 violates the range [1, 200000]

Test #8:

score: 0
Wrong Answer
time: 500ms
memory: 51564kb

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:

181947 167604 167604
126248 167604 167604
116508 167604 167604
77572 167604 167604
189796 167604 167604
32539 167604 167604
31161 167604 167604
88736 167604 167604
189194 167604 167604
199382 167604 167604
95130 167604 167604
99255 167604 167604
129420 167604 167604
139777 167604 167604
11005 167604...

result:

wrong answer Wrong answer on test 1

Test #9:

score: 0
Wrong Answer
time: 615ms
memory: 45248kb

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:

141796 7107 27232
181051 109653 199425
59455 50284 35744
50102 130361 28875
33135 181116 161848
88637 169934 85106
129492 76945 130795
65710 90715 186265
105187 64937 144848
155062 23869 124671
84782 35817 167918
43450 46422 7480
193611 82742 102475
150834 92303 38338
167560 75275 10364
26236 137993...

result:

wrong answer Wrong answer on test 1

Test #10:

score: 0
Wrong Answer
time: 611ms
memory: 45392kb

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:

26462 135279 172309
115844 191502 187823
77153 142861 81355
167769 94624 51830
170884 88035 176965
11608 185194 64977
5331 115054 76357
16214 101600 118957
35201 141386 113627
89477 101442 26107
100122 165252 132582
145411 98743 111633
21901 74622 10772
83219 175428 74198
26061 63251 33976
6211 6281...

result:

wrong answer Wrong answer on test 1