QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88914#5828. 游戏Larunatrecy10 276ms69652kbC++143.5kb2023-03-17 21:58:322023-03-17 21:58:34

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-17 21:58:34]
  • 评测
  • 测评结果:10
  • 用时:276ms
  • 内存:69652kb
  • [2023-03-17 21:58:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
struct edge
{
	int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
namespace tree
{
	int dep[N],st[2*N][20],tot=0;
	int lg[2*N],dfn[N];
	void dfs(int x,int pre)
	{
		st[++tot][0]=x;
		dfn[x]=tot;
		for(int i=link[x];i;i=e[i].next)
		{
			int y=e[i].y;
			if(y==pre)continue;
			dep[y]=dep[x]+1;
			dfs(y,x);
			st[++tot][0]=x; 
		}
	}
	inline int Min(int x,int y)
	{
		return dep[x]<dep[y]?x:y;
	}
	void Build()
	{
		dfs(1,0);
		for(int i=2;i<=tot;i++)lg[i]=lg[i>>1]+1;
		for(int k=1;k<=lg[tot];k++)
		for(int i=1;i+(1<<k)-1<=tot;i++)
		st[i][k]=Min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
	}
	inline int LCA(int x,int y)
	{
		x=dfn[x];y=dfn[y];
		if(x>y)swap(x,y);
		int k=lg[y-x+1];
		return Min(st[x][k],st[y-(1<<k)+1][k]);
	}
	inline int dist(int x,int y)
	{
		return dep[x]+dep[y]-2*dep[LCA(x,y)];
	}
}
int st,ed;
int n,m;
int A[N],B[N],fa[N];
void dfs(int x,int pre,int *D)
{
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		fa[y]=x;
		D[y]=D[x]+1;
		dfs(y,x,D);
	}
}
bool ins[N];
int seq[N];
int h[N];
void dfs2(int x,int pre)
{
	h[x]=0;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(ins[y]||y==pre)continue;
		dfs2(y,x);
		h[x]=max(h[x],h[y]+1);
	}
}
int qoj[N],dfn[N];
int cnt=0;
void dfs3(int x,int pre)
{
	qoj[++cnt]=x;
	dfn[x]=cnt;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(ins[y]||y==pre)continue;
		if(h[x]==h[y]+1)
		{
			dfs3(y,x);
			return;
		}
	}
}
int mx[N][20];
int lg[N];
inline int Max(int x,int y){return h[x]>h[y]?x:y;}
int x,y,z;
int query(int l,int r)
{
	int k=lg[r-l+1];
	return Max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int dft[N];
bool check(int a,int b,int c)
{
	if(b==0) 
	{
		x=seq[1];
		y=seq[a+1];
		z=seq[a+c+1];
		return 1;
	}
	int l=a+1,r=m-c;
	if(l>r)return 0;
	int o=query(l,r);
	if(h[o]<b)return 0;
	x=seq[dft[o]-a];
	y=qoj[dfn[o]+b];
	z=seq[dft[o]+c];
	return 1;
}
bool check(int x,int y,int z,int u,int v,int w)
{
	if(tree::dist(x,y)!=u)return 0;
	if(tree::dist(y,z)!=v)return 0;
	if(tree::dist(z,x)!=w)return 0;
	return 1;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}
	tree::Build();
	dfs(1,0,A);
	for(int i=1;i<=n;i++)
	if(A[i]>A[st])st=i;
	fa[st]=0;
	dfs(st,0,B);
	for(int i=1;i<=n;i++)
	if(B[i]>B[ed])ed=i;
	int o=ed;
	while(o)
	{
		ins[o]=1;
		seq[++m]=o;
		dft[o]=m;
		o=fa[o];
	}
	for(int i=1;i<=m;i++)
	{
		dfs2(seq[i],0);
		dfs3(seq[i],0);
		mx[i][0]=seq[i];
	}
	for(int i=2;i<=m;i++)lg[i]=lg[i>>1]+1;
	for(int k=1;k<=lg[m];k++)
	for(int i=1;i+(1<<k)-1<=m;i++)
	mx[i][k]=Max(mx[i][k-1],mx[i+(1<<(k-1))][k-1]); 
	int q;
	cin>>q;
	while(q--)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		int u=a,v=b,w=c;
		bool flag=0;
		int d=(a+b+c)/2;
		a=d-a;b=d-b;c=d-c;
		if(!flag)flag|=check(a,b,c);
		if(!flag)flag|=check(a,c,b);
		if(!flag)flag|=check(b,a,c);
		if(!flag)flag|=check(b,c,a);
		if(!flag)flag|=check(c,a,b);
		if(!flag)flag|=check(c,b,a);
		if(check(x,y,z,u,v,w))printf("%d %d %d\n",x,y,z);
		else if(check(x,z,y,u,v,w))printf("%d %d %d\n",x,z,y);
		else if(check(y,x,z,u,v,w))printf("%d %d %d\n",y,x,z);
		else if(check(y,z,x,u,v,w))printf("%d %d %d\n",y,z,x);
		else if(check(z,x,y,u,v,w))printf("%d %d %d\n",z,x,y);
		else if(check(z,y,x,u,v,w))printf("%d %d %d\n",z,y,x);
		else printf("-1\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

175 421 463
47 421 239
376 361 209
175 343 350
420 436 57
184 461 57
450 343 431
126 158 202
39 179 93
473 120 165
47 215 391
362 215 463
171 401 57
370 311 328
90 125 209
243 49 391
473 306 478
417 60 476
148 253 493
47 158 292
50 47 110
169 211 452
73 361 403
169 17 113
487 215 452
399 110 431
116...

result:

wrong answer Wrong answer on test 1

Test #2:

score: 0
Wrong Answer
time: 4ms
memory: 4224kb

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:

1443 1227 324
898 528 1026
230 886 324
769 870 1000
1343 692 1533
461 109 1118
506 1995 1026
1846 1030 1672
389 1390 464
1819 339 1301
692 29 1414
413 836 471
910 1574 1050
572 1201 152
572 664 722
898 158 1845
898 1001 1227
1846 989 666
1950 652 1672
1279 1848 1220
401 1480 145
436 1366 1630
278 14...

result:

wrong answer Wrong answer on test 1

Test #3:

score: 0
Wrong Answer
time: 141ms
memory: 47644kb

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:

143809 87763 44962

result:

wrong answer Wrong answer on test 1

Test #4:

score: 0
Wrong Answer
time: 150ms
memory: 47696kb

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:

176688 174571 95506

result:

wrong answer Wrong answer on test 1

Test #5:

score: 0
Wrong Answer
time: 145ms
memory: 47564kb

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:

98198 34411 27046
49857 39355 70450
64637 52145 69064
118391 129196 75453
146165 96028 32236
26201 194867 124636
106205 193249 151320
44996 36173 147780
10582 16928 147134
106757 197158 196326

result:

wrong answer Wrong answer on test 1

Test #6:

score: 0
Wrong Answer
time: 146ms
memory: 47384kb

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:

7480 145500 3363
27494 156481 156628
59297 134802 136664
139436 126929 4472
92990 79250 19984
19769 31684 84929
50600 77495 148651
10494 49868 79717
105707 12157 36244
50225 82672 155540

result:

wrong answer Wrong answer on test 1

Test #7:

score: 0
Wrong Answer
time: 257ms
memory: 69652kb

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:

1 145645 62949
38957 68760 1
1 115484 20705
36782 16671 1
1 41631 5656
28131 114616 1
114785 58614 1
94241 171869 1
1 174290 131964
154225 175188 1
139642 142541 1
21712 82073 1
1 20583 16556
83956 177239 1
1 99183 8150
12843 94979 1
117147 136758 1
1 93202 55604
26120 9655 1
1 70963 31750
95600 281...

result:

wrong answer Wrong answer on test 1

Test #8:

score: 10
Accepted
time: 242ms
memory: 47532kb

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:

183543 183543 178310
98115 98115 178310
36778 36778 178310
30537 30537 178310
169883 169883 178310
65826 65826 178310
31265 31265 178310
161066 161066 178310
129717 129717 178310
85 85 178310
98442 98442 178310
118809 118809 178310
183881 183881 178310
87348 87348 178310
186490 186490 178310
113946 ...

result:

ok Accepted!

Test #9:

score: 0
Wrong Answer
time: 276ms
memory: 47424kb

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:

34708 80097 81596
186401 66894 42045
95044 184795 140544
161190 165046 15891
181723 66610 196866
139020 119681 117148
177939 113149 151070
136800 83964 199684
193733 99848 165590
99034 75873 182287
44210 119888 197331
98649 44224 113772
59119 151223 34254
69646 3957 19165
122318 82137 79516
120870 9...

result:

wrong answer Wrong answer on test 1

Test #10:

score: 0
Wrong Answer
time: 271ms
memory: 47612kb

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:

115995 46612 19487
185226 74523 99574
85322 113594 143204
146957 25740 128773
89001 184978 83393
65929 163893 94172
180089 130689 195057
159412 166586 123029
139139 21175 181742
51547 134043 126401
160570 3992 172760
110479 17316 168064
8619 77703 156309
178898 95660 38381
67418 55180 171987
184141 ...

result:

wrong answer Wrong answer on test 1