QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125551 | #5828. 游戏 | orz_z | 0 | 529ms | 114380kb | C++14 | 6.6kb | 2023-07-16 20:32:05 | 2023-07-16 20:32:07 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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