QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125450 | #5828. 游戏 | orz_z | 20 | 664ms | 77396kb | C++14 | 5.4kb | 2023-07-16 18:27:40 | 2023-07-16 18:27:41 |
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) {
// cout << "jump : " << x << ' ' << d << ' ';
dF(i, 19, 0) if((d >> i) & 1) x = f[i][x];
// cout << x << '\n';
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 = 0;
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;
// while(!g[u].empty() && g[u].back() == 0) g[u].pop_back();
}
void dfs2(int u, int fa, int ln) {
if(fa && ln) {
g[u].pb(node(ln, fa, 0));
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;
for(int v : d[u]) if(v != fa) {
nw = 0;
if(g[u][0].v == v) nw = g[u][1].ln;
else nw = g[u][0].ln;
dfs2(v, u, nw + 1);
}
}
void init() {
dfs(1, 0), dfs2(1, 0, 0);
}
}
namespace CDQ {
int as[_];
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
void init() {
F(i, 1, q) {
F(j, 1, n) if(HG::g[j][0].ln >= qr[i].g[0].fi && HG::g[j][1].ln >= qr[i].g[1].fi && HG::g[j][2].ln >= qr[i].g[2].fi) {
as[i] = j; break;
}
}
}
}
namespace Gas {
int ans[_][3];
void init() {
F(i, 1, q) {
int x = CDQ::as[i];
// cout <<i <<" : " <<x << '\n';
F(j, 0, 2) if(HG::g[x][j].v2 == 0) {
ans[i][j] = Tree::jump(x, CDQ::qr[i].g[j].fi);
if(!ans[i][j]) ans[i][j] = x;
} else {
ans[i][j] = Tree::jump(HG::g[x][j].v2, HG::g[x][j].ln - CDQ::qr[i].g[j].fi);
if(!ans[i][j]) ans[i][j] = x;
}
// cout << "haha " << ans[i][0] << ' ' << ans[i][1] <<' ' << ans[i][2] <<'\n';
}
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();
// cout <<Tree::jump(9, 2) <<"!!\n";
q = ri();
F(i, 1, q) {
int x = ri(), y = ri(), z = ri();
CDQ::qr[i] = CDQ::qry(x, y, z);
}
// cout <<"ES\n";
CDQ::init();
// cout <<"ES\n";
Gas::init();
// Try;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 48064kb
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:
344 21 39 30 498 343 39 362 21 443 92 176 182 343 30 485 1 290 443 218 19 330 30 311 28 182 30 30 136 105 100 311 396 335 454 30 101 2 415 275 30 361 146 39 21 311 469 396 481 136 30 86 115 320 190 263 30 201 86 269 135 5 5 30 215 437 30 361 266 30 155 281 68 100 437 1 68 154 30 17 34 330 179 30 30 ...
result:
wrong answer Wrong answer on test 1
Test #2:
score: 0
Wrong Answer
time: 2ms
memory: 48500kb
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:
1816 2 1194 755 1685 55 1447 4 1 2 1979 2 1144 1022 1428 1899 540 1708 798 1262 1069 470 910 528 1095 474 427 1639 1179 1444 480 1144 1563 1434 191 307 898 1837 1262 652 676 1217 222 676 1990 860 1428 431 1217 1428 1022 192 910 1776 274 1686 976 1523 1264 584 1022 1049 681 1311 174 222 73 100 1727 1...
result:
wrong answer Wrong answer on test 4
Test #3:
score: 10
Accepted
time: 127ms
memory: 66896kb
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:
178310 71361 45838
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 114ms
memory: 63852kb
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:
114360 24899 74592
result:
ok Accepted!
Test #5:
score: 0
Wrong Answer
time: 97ms
memory: 66992kb
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:
127511 1448 35530 1108 137984 179117 130765 89886 119043 141295 148920 18947 103697 119571 171061 177088 66103 63736 112619 160226 68885 23757 63084 141497 22362 80194 21452 10715 129015 63023
result:
wrong answer Wrong answer on test 2
Test #6:
score: 0
Wrong Answer
time: 141ms
memory: 63688kb
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:
103373 133610 186702 138116 166333 11082 191314 176954 147915 175616 78768 7072 48857 25606 38226 55099 28349 60403 2 108830 2 56037 99474 92047 4713 148654 102596 113102 46567 140997
result:
wrong answer Wrong answer on test 7
Test #7:
score: 0
Time Limit Exceeded
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:
result:
Test #8:
score: 0
Wrong Answer
time: 159ms
memory: 77396kb
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:
1 1 2636 1 1 91489 1 1 131556 1 1 193525 1 1 153276 1 1 32244 1 1 71663 1 1 153610 1 1 30330 1 1 191610 1 1 78056 1 1 67678 1 1 132259 1 1 198452 1 1 92597 1 1 161955 1 1 69163 1 1 75484 1 1 140720 1 1 31098 1 1 85959 1 1 16443 1 1 153465 1 1 27042 1 1 78685 2 2 2 1 1 143360 2 2 2 1 1 17871 1 1 9506...
result:
wrong answer Wrong answer on test 26
Test #9:
score: 0
Wrong Answer
time: 406ms
memory: 77356kb
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:
112025 146456 474 47308 1349 40141 89812 141796 1349 474 28255 128707 112630 20433 65803 12514 1349 184266 57810 196360 161063 69602 139697 100348 148222 127971 474 21554 161772 136856 474 17832 124979 474 47675 83810 197141 75865 93742 91732 1349 161103 67960 1349 166223 19931 87678 1349 474 58494 ...
result:
wrong answer Wrong answer on test 1
Test #10:
score: 0
Wrong Answer
time: 664ms
memory: 77292kb
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:
115695 188714 98148 29794 33198 1611 38191 1611 162799 1611 69668 40330 140620 23159 839 1611 110338 171745 63484 126207 113689 114835 1611 61418 105489 63975 30626 92659 20471 146059 94700 164103 1611 183388 32400 39397 1611 84442 90561 3 162000 52656 19385 26094 1611 176991 170764 1611 154399 742 ...
result:
wrong answer Wrong answer on test 2