QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311984#5828. 游戏zlt100 ✓502ms145376kbC++147.7kb2024-01-23 07:29:022024-01-23 07:29:02

Judging History

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

  • [2024-01-23 07:29:02]
  • 评测
  • 测评结果:100
  • 用时:502ms
  • 内存:145376kb
  • [2024-01-23 07:29:02]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
typedef priority_queue< pii, vector<pii>, greater<pii> > pqi;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    for (; !isdigit(c); c = getchar()) ;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

void write(int x) {
	if (x > 9) {
		write(x / 10);
	}
	putchar('0' + x % 10);
}

const int maxn = 200100;
const int logn = 20;

int n, m, head[maxn], len, ans[maxn], ff[maxn][logn];
int dep[maxn], fa[maxn], sz[maxn], son[maxn], top[maxn];
bool vis[maxn];
pqi pq[maxn];

struct node {
	int x, y, z, id, u, v, w, op;
} a[maxn * 5], b[maxn * 5];

inline bool cmp(node a, node b) {
	if (a.x != b.x) {
		return a.x > b.x;
	} else if (a.y != b.y) {
		return a.y > b.y;
	} else if (a.z != b.z) {
		return a.z > b.z;
	} else {
		return a.op < b.op;
	}
}

inline bool cmp2(node a, node b) {
	return a.op < b.op || (a.op == b.op && a.id < b.id);
}

struct edge {
	int to, next;
} edges[maxn << 1];

void add_edge(int u, int v) {
	edges[++len].to = v;
	edges[len].next = head[u];
	head[u] = len;
}

inline pii getmx(pqi pq) {
	pii mx = make_pair(-1, -1);
	while (pq.size()) {
		mx = max(mx, pq.top());
		pq.pop();
	}
	return mx;
}

void dfs(int u, int fa) {
	pq[u].push(make_pair(0, u));
	pq[u].push(make_pair(0, u));
	pq[u].push(make_pair(0, u));
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa) {
			continue;
		}
		ff[v][0] = u;
		dfs(v, u);
		pii t = getmx(pq[v]);
		++t.fst;
		pq[u].push(t);
		while ((int)pq[u].size() > 3) {
			pq[u].pop();
		}
	}
}

void dfs2(int u, int fa, pii d) {
	// printf("u, d: %d %d\n", u, d);
	vector<int> son;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa) {
			continue;
		}
		son.pb(v);
	}
	pq[u].push(d);
	while ((int)pq[u].size() > 3) {
		pq[u].pop();
	}
	if (son.empty()) {
		return;
	}
	int len = (int)son.size();
	vector<pii> pre(len), suf(len);
	pre[0] = getmx(pq[son[0]]);
	for (int i = 1; i < len; ++i) {
		pre[i] = max(pre[i - 1], getmx(pq[son[i]]));
	}
	suf[len - 1] = getmx(pq[son[len - 1]]);
	for (int i = len - 2; ~i; --i) {
		suf[i] = max(suf[i + 1], getmx(pq[son[i]]));
	}
	for (int i = 0; i < len; ++i) {
		int v = son[i];
		pii mx = make_pair(-1, -1);
		if (i) {
			mx = max(mx, pre[i - 1]);
		}
		if (i + 1 < len) {
			mx = max(mx, suf[i + 1]);
		}
		++mx.fst;
		// printf("u, v: %d %d %d\n", u, v, mx);
		pii t = max(mx, d);
		++t.fst;
		dfs2(v, u, t);
	}
}

int dfs3(int u, int f, int d) {
	fa[u] = f;
	sz[u] = 1;
	dep[u] = d;
	int maxson = -1;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == f) {
			continue;
		}
		sz[u] += dfs3(v, u, d + 1);
		if (sz[v] > maxson) {
			son[u] = v;
			maxson = sz[v];
		}
	}
	return sz[u];
}

void dfs4(int u, int tp) {
	top[u] = tp;
	vis[u] = 1;
	if (!son[u]) {
		return;
	}
	dfs4(son[u], tp);
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (vis[v]) {
			continue;
		}
		dfs4(v, v);
	}
}

inline int qlca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) {
			swap(x, y);
		}
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	return x;
}

inline int qdis(int x, int y) {
	return dep[x] + dep[y] - dep[qlca(x, y)] * 2;
}

inline int jump(int x, int k) {
	if (!k) {
		return x;
	}
	for (int i = 18; ~i; --i) {
		if (k & (1 << i)) {
			x = ff[x][i];
		}
	}
	return x;
}

inline int kth(int x, int y, int k) {
	int lca = qlca(x, y), dis = qdis(x, y);
	if (k <= dep[x] - dep[lca]) {
		return jump(x, k);
	} else {
		return jump(y, dis - k);
	}
}

namespace BIT {
	int c[maxn];
	
	inline void update(int x, int d) {
		for (int i = (++x); i; i -= (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = (++x); i <= n + 1; i += (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
	
	inline void clear(int x) {
		for (int i = (++x); i; i -= (i & (-i))) {
			c[i] = 0;
		}
	}
}

void cdq(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) >> 1, p1 = l, p2 = mid + 1, tot = 0;
	cdq(l, mid);
	cdq(mid + 1, r);
	while (p1 <= mid && p2 <= r) {
		if (a[p1].y >= a[p2].y) {
			if (a[p1].op == 0) {
				BIT::update(a[p1].z, a[p1].id);
			}
			b[++tot] = a[p1++];
		} else {
			if (a[p2].op == 1) {
				ans[a[p2].id] = max(ans[a[p2].id], BIT::query(a[p2].z));
			}
			b[++tot] = a[p2++];
		}
	}
	while (p1 <= mid) {
		if (a[p1].op == 0) {
			BIT::update(a[p1].z, a[p1].id);
		}
		b[++tot] = a[p1++];
	}
	while (p2 <= r) {
		if (a[p2].op == 1) {
			ans[a[p2].id] = max(ans[a[p2].id], BIT::query(a[p2].z));
		}
		b[++tot] = a[p2++];
	}
	for (int i = l; i <= mid; ++i) {
		if (a[i].op == 0) {
			BIT::clear(a[i].z);
		}
	}
	for (int i = 1; i <= tot; ++i) {
		a[l + i - 1] = b[i];
	}
}

void solve() {
	n = read();
	for (int i = 1, u, v; i < n; ++i) {
		u = read();
		v = read();
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(1, -1);
	dfs2(1, -1, make_pair(0, 1));
	dfs3(1, -1, 1);
	dfs4(1, 1);
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i <= n; ++i) {
			ff[i][j] = ff[ff[i][j - 1]][j - 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		a[i].id = i;
		a[i].op = 0;
		a[i].x = pq[i].top().fst;
		a[i].u = pq[i].top().scd;
		pq[i].pop();
		a[i].y = pq[i].top().fst;
		a[i].v = pq[i].top().scd;
		pq[i].pop();
		a[i].z = pq[i].top().fst;
		a[i].w = pq[i].top().scd;
		swap(a[i].x, a[i].z);
		swap(a[i].u, a[i].w);
		// printf("%d %d %d\n", a[i].x, a[i].y, a[i].z);
		// printf("%d %d %d %d %d %d\n", a[i].x, a[i].y, a[i].z, a[i].u, a[i].v, a[i].w);
	}
	m = read();
	for (int i = 1, x, y, z; i <= m; ++i) {
		x = read();
		y = read();
		z = read();
		a[i + n].x = (x + y - z) / 2;
		a[i + n].y = (x + z - y) / 2;
		a[i + n].z = (y + z - x) / 2;
		a[i + n].u = x;
		a[i + n].v = y;
		a[i + n].w = z;
		vector<int> vc;
		vc.pb(a[i + n].x);
		vc.pb(a[i + n].y);
		vc.pb(a[i + n].z);
		sort(vc.begin(), vc.end(), greater<int>());
		a[i + n].x = vc[0];
		a[i + n].y = vc[1];
		a[i + n].z = vc[2];
		// printf("%d %d %d\n", a[i + n].x, a[i + n].y, a[i + n].z);
		a[i + n].id = i;
		a[i + n].op = 1;
	}
	sort(a + 1, a + n + m + 1, cmp);
	cdq(1, n + m);
	sort(a + 1, a + n + m + 1, cmp2);
	// for (int i = 1; i <= m; ++i) {
		// printf("%d\n", ans[i]);
	// }
	for (int i = 1; i <= m; ++i) {
		int k = ans[i];
		// printf("k: %d\n", k);
		// printf("%d %d %d\n", a[k].x, a[k].y, a[k].z);
		int u = a[k].u, v = a[k].v, w = a[k].w;
		// printf("u, v, w: %d %d %d\n", u, v, w);
		u = kth(k, u, a[i + n].x);
		v = kth(k, v, a[i + n].y);
		w = kth(k, w, a[i + n].z);
		int x = a[i + n].u, y = a[i + n].v, z = a[i + n].w;
		vector<int> vc;
		vc.pb(u);
		vc.pb(v);
		vc.pb(w);
		sort(vc.begin(), vc.end());
		bool flag = 1;
		do {
			u = vc[0];
			v = vc[1];
			w = vc[2];
			if (qdis(u, v) == x && qdis(u, w) == y && qdis(v, w) == z) {
				write(u);
				putchar(' ');
				write(v);
				putchar(' ');
				write(w);
				putchar('\n');
				flag = 0;
				break;
			}
		} while (next_permutation(vc.begin(), vc.end()));
		if (flag) {
			// printf("i: %d\n", i);
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 6ms
memory: 22264kb

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
28 222 451
478 342 285
126 480 101
69 395 421
451 500 158
126 48 2
178 311 497
458 69 215
190 345 174
306 497 356
183 74 270
156 500 54
124 342 399
17 333 285
497 48 356
355 345 28
345 35 456
154 35 253
1 200 138
370 343 500
227 262 78
68 399 332
136 210 344
73 390 78
500 190 116
242 125 ...

result:

ok Accepted!

Test #2:

score: 10
Accepted
time: 4ms
memory: 22300kb

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:

1789 2000 1188
474 546 688
372 1995 1733
1281 196 2000
1686 581 1992
1371 1093 913
798 1262 1738
1163 506 853
1382 1852 1023
38 158 118
749 1695 765
1799 1494 881
42 873 298
856 1326 1030
1757 1803 414
1104 1992 362
1700 1992 581
608 506 1830
564 1090 87
1445 1134 722
581 1237 875
1522 1526 1634
175...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 287ms
memory: 64560kb

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:

176708 81782 168087

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 280ms
memory: 62744kb

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:

175810 46532 145940

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 255ms
memory: 64512kb

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:

180520 9346 135354
158646 80535 198034
89804 171254 94007
123714 184299 81244
148655 16000 5609
58386 126517 158508
97550 172287 96137
74130 81905 96258
50011 196948 137585
101363 68079 27060

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 285ms
memory: 63952kb

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:

172960 7414 113000
105926 5911 67376
145762 163725 149803
150834 80567 138788
13622 59883 167844
71639 15272 162792
96055 190140 200000
88030 46058 177036
19508 69264 76493
154594 187048 86508

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 454ms
memory: 145376kb

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:

54356 200000 137052
200000 170197 131241
84517 200000 179296
183330 163219 200000
158370 200000 194345
85385 171870 200000
143829 200000 85216
200000 122372 28132
200000 25711 157674
200000 179037 24813
200000 197101 57460
117928 178289 200000
200000 179418 195973
22762 116045 200000
100818 200000 1...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 433ms
memory: 76912kb

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:

200000 200000 78491
200000 200000 154921
200000 200000 87965
200000 200000 146877
200000 200000 157332
200000 200000 21575
200000 200000 180354
200000 200000 3595
200000 200000 166228
200000 200000 181366
200000 200000 126439
200000 200000 31249
200000 200000 198084
200000 200000 37465
200000 200000...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 491ms
memory: 76760kb

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:

101158 4699 129019
122188 169049 148367
35744 50284 59455
35129 188915 130307
103710 6105 100492
153244 102610 65370
159416 117630 95990
101303 3170 166132
80157 20733 109441
21588 196385 138947
23113 11440 26690
9432 143302 32364
60196 129461 41465
159411 89834 178169
161810 17975 159598
73836 6057...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 502ms
memory: 76976kb

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:

130342 113757 154843
92863 57168 154856
109575 116762 138908
135095 162933 49164
117562 11674 98556
170730 166726 138621
168681 59820 12789
113773 136925 136303
667 192953 168274
23768 136906 78620
16999 36209 8569
102991 131266 179145
125732 121182 140325
199991 77105 155305
140659 146151 166841
14...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed