QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125554#5828. 游戏orz_z100 ✓480ms114380kbC++145.4kb2023-07-16 20:36:102023-07-16 20:36:14

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:36:14]
  • 评测
  • 测评结果:100
  • 用时:480ms
  • 内存:114380kb
  • [2023-07-16 20:36:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
#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 dF(i, a, b) for(int i = a; i >= (b); --i)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
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;
}
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 = -0x3f3f3f3f, 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, 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: 10
Accepted
time: 3ms
memory: 53740kb

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:

241 295 342
136 485 81
40 94 295
29 253 327
153 81 240
452 391 40
29 227 100
207 443 476
273 153 136
68 278 271
366 476 367
154 123 342
209 391 443
458 125 168
108 211 295
476 179 367
492 278 281
463 255 454
209 228 215
239 54 415
476 37 391
215 246 1
40 168 71
270 180 217
493 366 1
391 361 353
150 ...

result:

ok Accepted!

Test #2:

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

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:

1995 1000 418
528 898 1026
809 1000 1283
870 831 1000
692 1343 1533
1285 1111 1118
798 1262 1069
1563 1991 727
1277 270 1095
98 1968 439
29 692 1414
464 413 195
176 910 809
89 572 1001
664 572 722
158 1533 174
1001 1533 1343
989 1991 735
652 1950 1672
1848 1279 1220
1343 409 105
1458 368 664
1149 17...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 200ms
memory: 76684kb

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:

129269 64489 100672

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 192ms
memory: 76032kb

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:

178959 179424 99114

result:

ok Accepted!

Test #5:

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

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:

3342 124894 184390
162071 120193 183997
152222 8229 88432
82637 19743 158643
130904 128821 81839
30650 156280 106365
176928 166553 86152
122190 131183 102049
118065 31118 89716
20896 15094 64450

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 209ms
memory: 77472kb

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:

4996 120650 154910
178734 23008 118396
165347 101075 71617
120417 39144 152524
195824 177152 19728
35356 187288 4164
177748 143545 55210
145304 93881 177689
182677 81679 70439
64257 48141 7069

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 431ms
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:

167532 21888 84836
55033 84836 123792
179615 64132 84836
84836 104947 68166
120811 79181 84836
171321 84836 56706
84836 28665 143449
7208 84836 179076
195032 20743 152706
3649 24612 178836
155605 152706 13065
145197 84836 63125
80809 101391 84836
178119 84836 881
175869 76687 84836
166972 84836 7199...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 333ms
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:

56264 56264 198431
56264 56264 69907
56264 56264 38396
56264 56264 116398
56264 56264 155898
56264 56264 97600
56264 56264 117916
56264 56264 166037
56264 56264 181704
56264 56264 113485
56264 56264 92223
56264 56264 52543
56264 56264 120883
56264 56264 58275
56264 56264 136370
76081 76081 181394
56...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 480ms
memory: 89796kb

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:

80587 34708 144003
147087 81464 42045
104657 112119 167698
165046 74246 102483
142619 34588 160376
81857 53666 87450
113149 177939 151070
196768 112246 199684
155312 21334 5823
172100 54335 184300
119888 20580 66285
44224 98649 113772
33460 133493 71093
179652 37925 80938
171545 129932 159894
145161...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 475ms
memory: 89824kb

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:

194182 143829 23090
69433 125911 110500
25190 196233 150961
168078 110453 58034
147351 180513 158257
159306 61042 136728
129885 156467 145240
193468 167921 165250
117359 151623 2818
121069 171984 175606
77430 20207 35357
181728 35458 73863
178957 111415 35212
174554 58156 115379
146214 26323 173778
...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed