QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#125554 | #5828. 游戏 | orz_z | 100 ✓ | 480ms | 114380kb | C++14 | 5.4kb | 2023-07-16 20:36:10 | 2023-07-16 20:36:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
#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 dF(i, a, b) for(int i = a; i >= (b); --i)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
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;
}
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 = -0x3f3f3f3f, 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, 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;
}
详细
Test #1:
score: 10
Accepted
time: 3ms
memory: 53740kb
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 136 485 81 40 94 295 29 253 327 153 81 240 452 391 40 29 227 100 207 443 476 273 153 136 68 278 271 366 476 367 154 123 342 209 391 443 458 125 168 108 211 295 476 179 367 492 278 281 463 255 454 209 228 215 239 54 415 476 37 391 215 246 1 40 168 71 270 180 217 493 366 1 391 361 353 150 ...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 3ms
memory: 54680kb
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:
1995 1000 418 528 898 1026 809 1000 1283 870 831 1000 692 1343 1533 1285 1111 1118 798 1262 1069 1563 1991 727 1277 270 1095 98 1968 439 29 692 1414 464 413 195 176 910 809 89 572 1001 664 572 722 158 1533 174 1001 1533 1343 989 1991 735 652 1950 1672 1848 1279 1220 1343 409 105 1458 368 664 1149 17...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 200ms
memory: 76684kb
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:
129269 64489 100672
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 192ms
memory: 76032kb
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:
178959 179424 99114
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 213ms
memory: 77632kb
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:
3342 124894 184390 162071 120193 183997 152222 8229 88432 82637 19743 158643 130904 128821 81839 30650 156280 106365 176928 166553 86152 122190 131183 102049 118065 31118 89716 20896 15094 64450
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 209ms
memory: 77472kb
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:
4996 120650 154910 178734 23008 118396 165347 101075 71617 120417 39144 152524 195824 177152 19728 35356 187288 4164 177748 143545 55210 145304 93881 177689 182677 81679 70439 64257 48141 7069
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 431ms
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:
167532 21888 84836 55033 84836 123792 179615 64132 84836 84836 104947 68166 120811 79181 84836 171321 84836 56706 84836 28665 143449 7208 84836 179076 195032 20743 152706 3649 24612 178836 155605 152706 13065 145197 84836 63125 80809 101391 84836 178119 84836 881 175869 76687 84836 166972 84836 7199...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 333ms
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:
56264 56264 198431 56264 56264 69907 56264 56264 38396 56264 56264 116398 56264 56264 155898 56264 56264 97600 56264 56264 117916 56264 56264 166037 56264 56264 181704 56264 56264 113485 56264 56264 92223 56264 56264 52543 56264 56264 120883 56264 56264 58275 56264 56264 136370 76081 76081 181394 56...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 480ms
memory: 89796kb
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:
80587 34708 144003 147087 81464 42045 104657 112119 167698 165046 74246 102483 142619 34588 160376 81857 53666 87450 113149 177939 151070 196768 112246 199684 155312 21334 5823 172100 54335 184300 119888 20580 66285 44224 98649 113772 33460 133493 71093 179652 37925 80938 171545 129932 159894 145161...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 475ms
memory: 89824kb
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:
194182 143829 23090 69433 125911 110500 25190 196233 150961 168078 110453 58034 147351 180513 158257 159306 61042 136728 129885 156467 145240 193468 167921 165250 117359 151623 2818 121069 171984 175606 77430 20207 35357 181728 35458 73863 178957 111415 35212 174554 58156 115379 146214 26323 173778 ...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed