QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125551#5828. 游戏orz_z0 529ms114380kbC++146.6kb2023-07-16 20:32:052023-07-16 20:32:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 20:32:07]
  • 评测
  • 测评结果:0
  • 用时:529ms
  • 内存:114380kb
  • [2023-07-16 20:32:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
// #define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define each(i, v) for(auto i : v)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug debug("Passing [%s] in LINS %d\n", __FUNCTION__, __LINE__)
#define pb push_back
#define fi first
#define se second
#define Mry debug("%.3lf MB\n", (&Mbe - &Med) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
	int x = 0;
	bool t = 0;
	char c = getchar();
	while (c < '0' || c > '9') t |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return t ? -x : x;
}
inline void wi(int x) {
	if (x < 0) {
		putchar('-'), x = -x;
	}
	if (x > 9) wi(x / 10);
	putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
	wi(x), putchar(s);
}
bool Mbe;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;


namespace GAME {
	int n, q;
	vi d[_];
	namespace Tree {
		int f[20][_], dep[_];
		void dfs(int u, int fa) {
			dep[u] = dep[fa] + 1, f[0][u] = fa;
			for(int v : d[u]) if(v != fa) dfs(v, u);
		}
		void init() {
			dfs(1, 0);
			F(i, 1, 19) F(j, 1, n) f[i][j] = f[i - 1][f[i - 1][j]];
		}
		int jump(int x, int d) {
			dF(i, 19, 0) if((d >> i) & 1) x = f[i][x];
			return x;
		}
		int LCA(int u, int v) {
			if(dep[u] < dep[v]) swap(u, v);
			dF(i, 19, 0) if(dep[f[i][u]] >= dep[v]) u = f[i][u];
			if(u == v) return u;
			dF(i, 19, 0) if(f[i][u] != f[i][v]) u = f[i][u], v = f[i][v];
			return f[0][u];
		}
		int Dis(int u, int v) {
			return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);
		}
	}
	namespace HG {
		struct node {
			int ln, v, v2;
			node() {
			}
			node(int Ln = 0, int V = 0, int V2 = 0) {
				ln = Ln, v = V, v2 = V2;
			}
		};
		vector<node> g[_];
		int len[_], p[_], p2[_];
		int dfs(int u, int fa) {
			g[u].clear();
			len[u] = 0;
			int p = u;
			for(int v : d[u]) if(v != fa){
				int w = dfs(v, u);
				if(len[u] < len[v] + 1) {
					len[u] = len[v] + 1;
					p = w;
				}
				g[u].pb(node(len[v] + 1, v, w));
			}
			sort(g[u].begin(), g[u].end(), [&](node a, node b) { return a.ln > b.ln; });
			while(g[u].size() > 3) g[u].pop_back();
			while(g[u].size() < 3) g[u].pb(node(0, 0, u));
			if(d[u].size() == 1) return u;
			else return p;
		}
		void dfs2(int u, int fa, int ln, int k) {
			if(fa && ln && k) {
				g[u].pb(node(ln, fa, k));
				sort(g[u].begin(), g[u].end(), [&](node a, node b) { return a.ln > b.ln; });
			}
			while(g[u].size() > 3) g[u].pop_back();
			while(g[u].size() < 3) g[u].pb(node(0, 0, u));
			int nw = 0, nw2 = 0;
			for(int v : d[u]) if(v != fa) {
				nw = 0;
				if(g[u][0].v == v) nw = g[u][1].ln, nw2 = g[u][1].v2;
				else nw = g[u][0].ln, nw2 = g[u][0].v2;
				dfs2(v, u, nw + 1, nw2);
			}
		}
		void init() {
			dfs(1, 0), dfs2(1, 0, 0, 1);
		}
	}
	namespace CDQ {
		int as[_], tot;
		struct qry {
			int x, y, z, d, a, b, c; // a--u, b -- v, c -- w
			vector<pii> g;
			int pos[3];
			qry() {}
			qry(int X, int Y, int Z) {
				x = X, y = Y, z = Z;
				d = (x + y + z) / 2;
				a = d - z, b = d- y, c = d - x;
				g.pb({a, 0}), g.pb({b, 1}), g.pb({c, 2});
				sort(g.begin(), g.end(), [&](pii a, pii b) { return a > b; });
				F(i, 0, 2) pos[g[i].se] = i;
			}
		} qr[_];
		// find u, st. g[u][0] >= a, g[u][1] >= b, g[u][c] >= c
		struct node {
			int a, b, c, id;
		} t[_], qr2[_], T[_ << 1];
		void solve(int l, int r) {
			if(l == r) return;
			int mid = (l + r) >> 1;
			solve(l, mid), solve(mid + 1, r);
			int mx = -inf, Id = -1, R = r + 1;
			dF(i, mid, l) if(T[i].id < 0) {
				while(R - 1 >= mid + 1 && (T[R - 1].id < 0 || T[R - 1].b > T[i].b)) {
					R--;
					if(T[R].id > 0 && T[R].b > T[i].b) if(T[R].c > mx) { mx = T[R].c, Id = T[R].id; }
				}
				if(Id > 0 && mx > T[i].c) as[-T[i].id] = Id;
			}
			sort(T + l, T + r + 1, [&](node a, node b) { return (a.b == b.b) ? a.c < b.c : a.b < b.b; });
		}
		void init() {
			F(i, 1, n) t[i].a = HG::g[i][0].ln, t[i].b = HG::g[i][1].ln, t[i].c = HG::g[i][2].ln, t[i].id = i;
			F(i, 1, n) cout << t[i].a << ' ' << t[i].b << '\n';
			F(i, 1, q) qr2[i].a = qr[i].g[0].fi - 1, qr2[i].b = qr[i].g[1].fi - 1, qr2[i].c = qr[i].g[2].fi - 1, qr2[i].id = -i;
			F(i, 1, n) T[i] = t[i];
			tot = n;
			F(i, 1, q) T[++tot] = qr2[i];
			sort(T + 1, T + tot + 1, [&](node a, node b) {
				if(a.a == b.a) {
					if(a.b == b.b) return a.c < b.c;
					return a.b < b.b;
				} return a.a < b.a;
			});
			solve(1, tot);
		}
	}
	namespace Gas {
		int ans[_][3];
		void init() {
			F(i, 1, q) {
				int x = CDQ::as[i];
				F(j, 0, 2) {
					assert(x);
//					cout << i << " :: " << x <<"!!\n";
//					assert(HG::g[x][j].ln >= CDQ::qr[i].g[j].fi);
					if(HG::g[x][j].ln == 0) {
						ans[i][j] = x;
					}
					else if(HG::g[x][j].v == Tree::f[0][x]) {
						ans[i][j] = (CDQ::qr[i].g[j].fi < Tree::dep[x]) ? Tree::jump(x, CDQ::qr[i].g[j].fi) : Tree::jump(HG::g[x][j].v2, HG::g[x][j].ln - CDQ::qr[i].g[j].fi);
//						assert(ans[i][j]);
						if(!ans[i][j]) {
							cout << CDQ::qr[i].g[j].fi << " " << Tree::dep[x] << " " << HG::g[x][j].ln << " " << HG::g[x][j].v2 << " " << x << "!!!!!\n";
						}
					} else {
						ans[i][j] = Tree::jump(HG::g[x][j].v2, HG::g[x][j].ln - CDQ::qr[i].g[j].fi);
						assert(ans[i][j]);
					}
				}
			}
			F(i, 1, q) cout << ans[i][CDQ::qr[i].pos[0]] << ' ' << ans[i][CDQ::qr[i].pos[1]] << ' ' << ans[i][CDQ::qr[i].pos[2]] << '\n';
		}
	}
} using namespace GAME;
bool Med;
signed main() {
	// Mry;
	n = ri();
	F(i, 1, n - 1) {
		int u = ri(), v  =ri();
		d[u].pb(v), d[v].pb(u);
	}
	Tree::init(), HG::init();
	q = ri();
	F(i, 1, q) {
		int x = ri(), y = ri(), z = ri();
		CDQ::qr[i] = CDQ::qry(x, y, z);
	}
	CDQ::init();
	Gas::init();
	// Try;
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 54600kb

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:

76 13
72 16
60 17
75 7
74 18
73 5
58 42
95 1
73 4
88 10
58 18
85 4
67 35
73 6
88 1
65 35
89 13
69 13
60 17
83 13
78 4
55 0
85 11
62 16
65 14
96 0
55 1
71 31
85 17
54 48
70 7
75 2
71 7
66 11
70 7
59 41
92 10
81 15
53 47
78 24
84 0
64 18
68 10
86 12
71 5
82 14
70 30
62 40
68 34
102 0
71 6
65 11
55 47
...

result:

wrong answer Wrong answer on test 1

Test #2:

score: 0
Wrong Answer
time: 9ms
memory: 54488kb

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:

347 0
320 16
223 28
267 81
219 32
311 10
216 0
318 27
290 73
299 13
289 74
256 17
228 36
294 60
274 38
215 0
318 3
315 4
254 47
314 31
216 0
249 9
241 59
243 57
318 45
293 19
310 53
265 71
249 99
265 54
249 2
224 27
297 51
303 42
315 8
255 32
194 6
282 5
309 10
340 15
254 65
277 10
213 60
262 101
26...

result:

wrong answer Integer 0 violates the range [1, 2000]

Test #3:

score: 0
Wrong Answer
time: 225ms
memory: 76088kb

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:

3880 18
3821 342
4142 718
4441 11
3717 131
3481 410
4862 116
4055 114
4605 31
4310 209
3490 167
3508 187
4236 242
4090 460
3745 1223
3585 738
4067 128
3592 1018
3491 702
4009 504
4609 370
4873 672
3413 372
4656 540
4181 45
4041 698
4130 428
4583 211
3865 1331
3991 147
5186 359
3647 381
4225 59
5264 ...

result:

wrong answer Wrong answer on test 1

Test #4:

score: 0
Wrong Answer
time: 208ms
memory: 76844kb

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:

4246 16
4317 12
4000 1907
4006 499
3921 285
4180 137
4601 2
4687 113
3081 1127
3406 868
3553 2253
4175 811
4555 345
4633 177
4008 482
4111 112
4135 787
4277 0
4569 325
3598 1262
4029 212
4673 658
3350 977
4507 290
3799 475
4142 98
3635 855
4539 108
4568 13
3490 338
4568 123
4621 52
3579 131
3792 70
...

result:

wrong answer Wrong answer on test 1

Test #5:

score: 0
Wrong Answer
time: 236ms
memory: 76196kb

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:

5905 137
4782 121
4505 9
4365 636
4096 354
5078 266
4102 67
3973 1665
4311 86
5052 372
4820 272
4625 98
4693 346
4193 153
5653 1211
4929 547
5887 274
3631 562
4363 937
4091 28
4042 309
4097 942
4173 141
5048 35
4894 37
4609 164
4510 319
4781 156
4415 185
4106 967
4387 614
5448 281
5004 890
4304 1172...

result:

wrong answer Wrong answer on test 1

Test #6:

score: 0
Wrong Answer
time: 218ms
memory: 77244kb

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:

4327 49
3096 406
3820 236
3335 705
3461 365
3719 89
4223 98
4214 107
3389 437
3843 329
3835 200
3287 1150
4076 159
3533 628
3623 366
3120 989
3547 774
4181 134
3574 237
4345 254
3367 57
3023 878
4162 187
3918 139
3296 13
3463 1028
3760 122
3518 789
4458 451
3870 841
4135 241
3648 346
3654 92
3246 13...

result:

wrong answer Wrong answer on test 1

Test #7:

score: 0
Wrong Answer
time: 437ms
memory: 114380kb

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:

199999 0
199998 1
199997 2
199996 3
199995 4
199994 5
199993 6
199992 7
199991 8
199990 9
199989 10
199988 11
199987 12
199986 13
199985 14
199984 15
199983 16
199982 17
199981 18
199980 19
199979 20
199978 21
199977 22
199976 23
199975 24
199974 25
199973 26
199972 27
199971 28
199970 29
199969 30
...

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #8:

score: 0
Wrong Answer
time: 392ms
memory: 89932kb

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:

4180 1817
5037 544
4519 128
4618 29
3958 333
5517 137
5050 54
5053 1375
5165 18
4641 293
5190 81
4577 1860
4297 402
5005 126
4310 497
4943 664
5289 352
4896 371
4235 896
3935 766
4400 16
3804 354
5006 364
5232 270
5713 182
4671 703
4715 193
4069 274
5871 566
3903 362
5032 527
5013 149
4898 69
3998 1...

result:

wrong answer Wrong answer on test 1

Test #9:

score: 0
Wrong Answer
time: 529ms
memory: 89888kb

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:

3678 316
4189 842
3169 1298
3842 8
4074 230
4159 225
4040 57
4138 149
4714 396
3607 147
3334 363
3859 553
3699 264
3967 10
4518 686
3519 341
4252 29
4026 392
3446 526
4115 210
4596 602
3798 929
4447 163
4832 13
4763 282
4189 234
4051 1073
3772 187
4615 718
3994 14
3540 1970
3893 132
4005 276
4156 82...

result:

wrong answer Wrong answer on test 1

Test #10:

score: 0
Wrong Answer
time: 522ms
memory: 89716kb

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:

3150 193
3397 337
3587 616
3286 196
3371 299
3029 321
3431 167
3768 95
3762 380
3581 0
4024 363
5002 288
3712 113
3465 17
3381 226
3590 386
3361 946
3518 41
3380 976
3664 229
3703 722
4538 323
3908 655
3476 130
3431 90
3126 138
4415 875
3082 1094
4166 10
3320 48
3488 71
3748 280
4379 236
3290 372
37...

result:

wrong answer Wrong answer on test 1