QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#311984 | #5828. 游戏 | zlt | 100 ✓ | 502ms | 145376kb | C++14 | 7.7kb | 2024-01-23 07:29:02 | 2024-01-23 07:29:02 |
Judging History
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