QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90696 | #5828. 游戏 | dispensable | 100 ✓ | 781ms | 104368kb | C++14 | 6.6kb | 2023-03-24 19:42:21 | 2023-03-24 19:42:22 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int MAXN = 400010;
int N, Q;
int tot, head[MAXN];
struct Edge {
int to, nxt;
} edge[MAXN];
void add(int u, int v) {
edge[++tot].to = v, edge[tot].nxt = head[u]; head[u] = tot;
}
int fa[MAXN][21], dep[MAXN], son[MAXN], len[MAXN];
void dfs(int u, int father) {
fa[u][0] = father, dep[u] = dep[father] + 1;
for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].to;
if (v == father) continue;
dfs(v, u);
if (len[u] < len[v] + 1) {
len[u] = len[v] + 1;
son[u] = v;
}
}
}
int dfn[MAXN], rnk[MAXN], dfncnt;
void Dfs(int u, int father) {
rnk[dfn[u] = ++dfncnt] = u;
if (son[u]) Dfs(son[u], u);
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].to;
if (v != father and v != son[u])
Dfs(v, u);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--)
if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i--)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int dis(int x, int y) {
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
int f[MAXN][4], to[MAXN][4];
void dfs1(int u, int father) {
vector<pii>D;
D.emplace_back(0, u), D.emplace_back(0, u), D.emplace_back(0, u);
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].to;
if (v == father) continue;
dfs1(v, u); D.emplace_back(f[v][0] + 1, v);
}
sort(D.begin(), D.end(), [](pii x, pii y) {
return x.fir > y.fir;
});
for (int i = 0; i < 3; i++)
f[u][i] = D[i].fir, to[u][i] = D[i].sec;
}
void dfs2(int u, int father) {
if (!father) f[u][3] = 0, to[u][3] = u;
else {
f[u][3] = f[father][3] + 1, to[u][3] = to[father][3];
if (f[father][0] == f[u][0] + 1) {
if (f[u][3] < f[father][1] + 1)
f[u][3] = f[father][1] + 1, to[u][3] = to[father][1];
} else {
if (f[u][3] < f[father][0] + 1)
f[u][3] = f[father][0] + 1, to[u][3] = to[father][0];
}
}
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].to;
if (v == father) continue;
dfs2(v, u);
}
}
struct Query {
int x, y, z;
} q[MAXN];
struct Node {
int opt, x, y, z, tim;
} a[MAXN], b[MAXN];
int aans[MAXN];
vector<Query>query[MAXN];
void cdq(int l, int r) {
if (l == r) return ;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
int L = l, R = mid + 1, cnt = l, Max = 0;
while (L <= mid and R <= r) {
if (a[L].y > a[R].y or (a[L].y == a[R].y and a[L].z >= a[R].z)) {
if (a[L].opt == 1)
if (a[Max].z <= a[L].z) Max = L;
b[cnt++] = a[L++];
}
else {
if (a[R].opt == 2)
if (a[R].z <= a[Max].z) aans[a[R].tim] = a[Max].tim;
b[cnt++] = a[R++];
}
}
while (R <= r) {
if (a[R].opt == 2)
if (a[R].z <= a[Max].z) aans[a[R].tim] = a[Max].tim;
b[cnt++] = a[R++];
}
while (L <= mid)
b[cnt++] = a[L++];
for (int i = l; i <= r; i++) a[i] = b[i];
}
int jump(int x, int step) {
for (int i = 20; i >= 0; i--)
if ((step >> i) & 1) x = fa[x][i];
return x;
}
int ans[MAXN][3], Ans[MAXN][3];
int main() {
N = read();
for (int i = 1; i < N; i++) {
int u = read(), v = read();
add(u, v), add(v, u);
}
dfs(1, 0), Dfs(1, 0);
dfs1(1, 0), dfs2(1, 0);
for (int i = 1; i <= N; i++) {
vector<pii>D; D.clear();
for (int j = 0; j <= 3; j++) D.emplace_back(f[i][j], to[i][j]);
sort(D.begin(), D.end(), [](pii x, pii y) {
return x.fir > y.fir;
});
for (int j = 0; j <= 2; j++) f[i][j] = D[2 - j].fir, to[i][j] = D[2 - j].sec;
}
for (int i = 1; i <= N; i++)
a[i] = (Node) { 1, f[i][0], f[i][1], f[i][2], i };
Q = read();
for (int i = 1; i <= Q; i++) {
int x = read(), y = read(), z = read(); static int p[3]; q[i] = (Query) {x, y, z};
p[0] = (y + z - x) / 2, p[1] = (x + z - y) / 2, p[2] = (x + y - z) / 2;
sort(p, p + 3);
a[N + i] = (Node) { 2, p[0], p[1], p[2], i };
}
sort(a + 1, a + N + Q + 1, [](Node x, Node y) {
return x.x != y.x ? x.x > y.x : (x.y != y.y ? x.y > y.y : (x.z != y.z ? x.z > y.z : x.opt < y.opt));
});
a[0] = (Node) { 1, -1, -1, -1, 0 };
cdq(1, N + Q);
for (int i = 1; i <= Q; i++) {
assert(aans[i]);
int u = aans[i]; static int p[4];
int x = q[i].x, y = q[i].y, z = q[i].z;
p[0] = (y + z - x) / 2, p[1] = (x + z - y) / 2, p[2] = (x + y - z) / 2;
sort(p, p + 3);
for (int j = 0; j <= 2; j++) {
if (p[j] == 0) {
ans[i][j] = u;
continue;
}
if (fa[to[u][j]][0] == u) {
ans[i][j] = rnk[dfn[to[u][j]] + p[j] - 1];
} else {
if (dep[u] - dep[to[u][j]] == f[u][j]) {
ans[i][j] = jump(u, p[j]);
} else {
int v = fa[to[u][j]][0];
if (dep[u] - dep[v] >= p[j])
ans[i][j] = jump(u, p[j]);
else
ans[i][j] = rnk[dfn[to[u][j]] + p[j] - (dep[u] - dep[v]) - 1];
}
}
}
for (int j = 0; j <= 2; j++) p[j] = j;
do {
bool flag = true;
flag &= dis(ans[i][p[0]], ans[i][p[1]]) == x;
flag &= dis(ans[i][p[0]], ans[i][p[2]]) == y;
flag &= dis(ans[i][p[1]], ans[i][p[2]]) == z;
if (flag) {
for (int j = 0; j <= 2; j++)
Ans[i][j] = ans[i][p[j]];
break;
}
//cerr << p[0] << " " << p[1] << " " << p[2] << "\n";
} while (next_permutation(p, p + 3));
}
for (int i = 1; i <= Q; i++) {
for (int j = 0; j <= 2; j++)
printf("%d ", Ans[i][j]);
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 0ms
memory: 13112kb
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 201 280 94 40 94 295 126 480 101 297 386 305 116 376 424 241 30 84 261 292 360 248 297 346 132 60 87 366 360 427 183 74 270 74 376 390 124 342 399 108 211 295 360 200 427 477 60 431 60 417 476 62 417 110 17 48 219 64 68 476 110 298 331 68 399 332 179 70 168 123 16...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 8ms
memory: 13676kb
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:
1093 1686 1733 474 546 688 1425 1528 1329 308 1144 1686 809 1887 758 1501 128 892 798 1262 1738 1065 1784 418 965 1788 386 1329 979 1383 749 1695 765 867 1070 1338 1717 232 793 216 1091 1556 886 1091 895 894 758 1798 109 758 1887 608 506 1830 393 1118 86 597 1105 134 466 1703 189...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 148ms
memory: 52008kb
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:
34526 187920 126136
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 165ms
memory: 52020kb
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:
124016 118230 38009
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 170ms
memory: 52332kb
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:
86732 82102 128046 88430 178958 77240 152222 8229 88432 82637 19743 158643 2255 55912 104975 82263 198593 109139 57427 140014 194500 116081 34080 51401 102355 132383 56487 190535 171087 78434
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 170ms
memory: 52096kb
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:
78196 24538 195329 61656 110387 9495 116888 61263 21725 137515 39144 152524 195824 177152 19728 102804 84168 108282 35006 110558 27213 100096 93881 177689 62609 105097 127333 64257 48141 90870
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 667ms
memory: 104368kb
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:
40974 186618 123670 198128 168325 129369 73546 189029 168325 168325 148214 184995 132350 173980 168325 81840 168325 196455 142430 198601 83817 10055 87683 181923 184756 10467 142430 189288 168325 14101 171224 168325 28684 107964 168325 190036 172352 151770 168325 180966 87683 3728 7729...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 350ms
memory: 67644kb
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:
178310 178310 183543 178310 178310 98115 178310 178310 36778 178310 178310 30537 178310 178310 169883 178310 178310 65826 178310 178310 31265 178310 178310 161066 178310 178310 129717 178310 178310 85 178310 178310 98442 178310 178310 118809 178310 178310 183881 178310 178310 87348 178...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 781ms
memory: 67532kb
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:
174856 71977 179574 3000 92997 150200 131745 178675 129413 8059 130361 28875 37393 59391 45678 42489 185493 12143 66024 107670 120658 10044 8498 121963 154803 72889 112576 82106 34224 127016 63867 80406 46292 163519 91560 155503 98542 88190 168671 13820 79772 56998 193797 136088 78237 ...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 732ms
memory: 67412kb
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:
135279 172309 119889 91745 39778 86165 174795 48231 61661 45021 101167 129885 129807 175058 144479 192745 159146 67647 27117 17150 39942 187426 29159 22043 33903 148821 19178 33905 3886 131706 132582 157902 165252 90388 100828 120122 74622 10772 21901 23433 20382 11390 95136 59440 7634...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed