QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#318999 | #5828. 游戏 | KiharaTouma | 100 ✓ | 383ms | 127592kb | C++23 | 9.9kb | 2024-02-01 14:42:01 | 2024-02-01 14:42:02 |
Judging History
answer
//qoj5828
#include <bits/stdc++.h>
using namespace std; typedef long long ll; namespace FastIO {
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc() { if (__builtin_expect(_read_ptr == _read_ptr_end, false)) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;} return *_read_ptr++; }
INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } }
INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; inline bool _isdigit(char c) { return (c & 16) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; }
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer; template <class T> INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed; template <class T> INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <> INLINE_V constexpr bool _is_integer<__int128> = true; template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true; template <> INLINE_V constexpr bool _is_signed<__int128> = true; template <> INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
inline void read(char &c) { do c = gc(); while (!_isgraph(c)); } inline void read_cstr(char *s) { char c = gc(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) s.push_back(c), c = gc(); }
template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void read(T &x) { char c = gc(); bool f = true; x = 0; while (!_isdigit(c)) { if (c == 45) f = false; c = gc(); }
if (f) while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); else while (_isdigit(c)) x = x * 10 - (c & 15), c = gc(); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void read(T &x) { char c = gc(); while (!_isdigit(c)) c = gc(); x = 0; while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); }
inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while (*s) pc(*s++); } inline void write(const string &s) { for (char c : s) pc(c); } template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; if (x >= 0) do buffer[digits++] = (x % 10) | 48, x /= 10; while (x);
else { pc(45); do buffer[digits++] = -(x % 10) | 48, x /= 10; while (x); } while (digits) pc(buffer[--digits]); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; do buffer[digits++] = (x % 10) | 48, x /= 10; while (x); while (digits) pc(buffer[--digits]); }
template <int N> struct _tuple_io_helper { template <class... T> static inline void _read(tuple<T...> &x) { _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x)); } };
template <> struct _tuple_io_helper<1> { template <class... T> static inline void _read(tuple<T...> &x) { read(get<0>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { write(get<0>(x)); } };
template <class... T> inline void read(tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_read(x); } template <class... T> inline void write(const tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_write(x); }
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); } template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first), pc(32), write(x.second); }
template <class T1, class... T2> inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template <class... T> inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template <class T1, class... T2> inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template <class... T> inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template <class T> inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template <class T1, class... T2> inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template <class... T> inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template <class... T> inline void println(const T &...x) { print(x...), pc(10); } template <class... T> inline void printk(const T &...x) { print(x...), pc(32); } template <class... T> inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; void solve();int main(){ solve(); return 0; }
const int N = 2e5 + 10;
int n, q, dep[N], mxd[N], mxo[N], f[N][4], fat[N][20];
int qu[N], qv[N], qw[N], au[N], av[N], aw[N], t[N*4], rt[N*4];
vector<pair<int, pair<int, int> > > ad[N], qr[N];
pair<int, int> fr[N][4];
vector<int> g[N];
void dfs1(int x, int fa){
mxd[x] = dep[x] = dep[fa] + 1;
mxo[x] = x;
fat[x][0] = fa;
for(int i = 1; i < 20; ++ i){
fat[x][i] = fat[fat[x][i-1]][i-1];
}
for(int y : g[x]){
if(y == fa){
continue;
}
dfs1(y, x);
pair<int, pair<int, int> > tmp[5];
for(int i = 0; i < 4; ++ i){
tmp[i] = make_pair(f[x][i], fr[x][i]);
}
tmp[4] = make_pair(mxd[y], make_pair(y, mxo[y]));
sort(tmp, tmp + 5);
reverse(tmp, tmp + 5);
for(int i = 0; i < 4; ++ i){
tie(f[x][i], fr[x][i]) = tmp[i];
}
if(mxd[y] > mxd[x]){
mxd[x] = mxd[y];
mxo[x] = mxo[y];
}
}
}
void dfs2(int x, int fa){
for(int y : g[x]){
if(y == fa){
continue;
}
pair<int, pair<int, int> > tmp[5];
for(int i = 0; i < 4; ++ i){
tmp[i] = make_pair(max(0, f[y][i] - dep[y]), fr[y][i]);
}
if(fr[x][0].first != y){
tmp[4] = make_pair(f[x][0] + 1, make_pair(x, fr[x][0].second));
} else {
tmp[4] = make_pair(f[x][1] + 1, make_pair(x, fr[x][1].second));
}
sort(tmp, tmp + 5);
reverse(tmp, tmp + 5);
for(int i = 0; i < 4; ++ i){
tie(f[y][i], fr[y][i]) = tmp[i];
}
dfs2(y, x);
}
}
int lca(int x, int y){
if(dep[x] < dep[y]){
swap(x, y);
}
for(int i = 19; i >= 0; -- i){
if(dep[fat[x][i]] >= dep[y]){
x = fat[x][i];
}
}
if(x == y){
return x;
}
for(int i = 19; i >= 0; -- i){
if(fat[x][i] != fat[y][i]){
x = fat[x][i];
y = fat[y][i];
}
}
return fat[x][0];
}
int jmp(int x, int d){
for(int i = 19; i >= 0; -- i){
if(d & (1 << i)){
x = fat[x][i];
}
}
return x;
}
int mv(int x, int y, int d){
int l = lca(x, y);
if(dep[x] - dep[l] < d){
d -= dep[x] - dep[l];
return mv(y, l, dep[y] - dep[l] - d);
} else {
return jmp(x, d);
}
}
void add(int p, int l, int r, int x, int v, int rr){
if(l == r){
if(v > t[p]){
t[p] = v;
rt[p] = rr;
}
} else {
int mid = l + r >> 1;
if(x <= mid){
add(p<<1, l, mid, x, v, rr);
} else {
add(p<<1|1, mid+1, r, x, v, rr);
}
if(t[p<<1] > t[p<<1|1]){
t[p] = t[p<<1];
rt[p] = rt[p<<1];
} else {
t[p] = t[p<<1|1];
rt[p] = rt[p<<1|1];
}
}
}
pair<int, int> ask(int p, int l, int r, int ql, int qr){
if(qr < l || r < ql){
return make_pair(-114, 0);
} else if(ql <= l && r <= qr){
return make_pair(t[p], rt[p]);
} else {
int mid = l + r >> 1;
return max(ask(p<<1, l, mid, ql, qr), ask(p<<1|1, mid+1, r, ql, qr));
}
}
void solve(){
read(n);
for(int i = 1; i < n; ++ i){
int u, v;
read(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, 0);
for(int i = 0; i < 4; ++ i){
if(f[1][i] > 0){
-- f[1][i];
} else {
f[1][i] = 0;
fr[1][i] = make_pair(1, 1);
}
}
dfs2(1, 0);
for(int i = 1; i <= n; ++ i){
if(!f[i][1]){
continue;
fr[i][1] = make_pair(i, i);
}
if(!f[i][2]){
fr[i][2] = make_pair(i, i);
}
ad[f[i][0]].emplace_back(f[i][1], make_pair(f[i][2], i));
ad[f[i][0]].emplace_back(f[i][2], make_pair(f[i][1], i));
ad[f[i][1]].emplace_back(f[i][0], make_pair(f[i][2], i));
ad[f[i][1]].emplace_back(f[i][2], make_pair(f[i][0], i));
ad[f[i][2]].emplace_back(f[i][0], make_pair(f[i][1], i));
ad[f[i][2]].emplace_back(f[i][1], make_pair(f[i][0], i));
}
read(q);
for(int i = 1; i <= q; ++ i){
int x, y, z, t[3];
read(x, y, z);
t[0] = (x + y - z) / 2;
t[1] = (x + z - y) / 2;
t[2] = (y + z - x) / 2;
qu[i] = t[0];
qv[i] = t[1];
qw[i] = t[2];
qr[t[0]].emplace_back(t[1], make_pair(t[2], i));
}
memset(t, -1, sizeof(t));
for(int i = n; i >= 0; -- i){
for(auto j : ad[i]){
add(1, 0, n, j.first, j.second.first, j.second.second);
}
for(auto j : qr[i]){
auto x = ask(1, 0, n, j.first, n);
if(x.first >= j.second.first){
au[j.second.second] = x.second;
}
}
}
for(int i = 1; i <= q; ++ i){
int r = au[i];
int a1 = (qu[i] > qv[i] ? 0 : 1) + (qu[i] > qw[i] ? 0 : 1);
int a2 = (qv[i] >= qu[i] ? 0 : 1) + (qv[i] > qw[i] ? 0 : 1);
int a3 = (qw[i] >= qu[i] ? 0 : 1) + (qw[i] >= qv[i] ? 0 : 1);
int x = mv(fr[r][a1].second, r, f[r][a1] - qu[i]);
int y = mv(fr[r][a2].second, r, f[r][a2] - qv[i]);
int z = mv(fr[r][a3].second, r, f[r][a3] - qw[i]);
println(x, y, z);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 2ms
memory: 18184kb
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 361 278 175 29 253 327 297 386 305 57 64 461 29 227 100 207 443 476 399 268 30 215 116 257 366 360 427 183 74 270 57 93 401 275 463 361 17 333 285 242 306 82 477 60 431 496 247 211 74 323 39 17 48 219 202 50 110 227 262 78 478 454 80 270 180 217 123 165 106 30 168 366 242 125 ...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 6ms
memory: 18620kb
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:
169 44 1600 474 546 688 1425 1118 1633 555 356 1152 134 1840 1973 1252 608 1495 798 1262 1738 1065 1784 418 1283 211 1532 1498 608 971 223 620 217 1495 261 1201 1717 232 793 856 1326 1030 886 1091 895 809 680 1920 1565 680 865 1672 727 1960 1094 469 1498 1445 1134 722 466 1703 1897 265 1734 1043 282...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 246ms
memory: 71540kb
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:
776 87237 28828
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 229ms
memory: 72204kb
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: 226ms
memory: 71984kb
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:
151908 100567 8721 83205 59848 186152 77586 20873 189692 82637 19743 158643 57450 78922 97078 8412 35694 91454 150386 21717 136838 36808 82816 94104 176048 3051 100174 66824 169604 86044
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 226ms
memory: 71740kb
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:
106922 97132 138890 76437 85688 53605 116888 61263 21725 40657 108839 54522 195824 177152 19728 112642 70748 24715 183291 31534 40603 100096 93881 177689 153396 122160 23021 64257 48141 90870
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 319ms
memory: 127592kb
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:
182696 37052 100000 1 29804 68760 194779 79296 100000 20112 40223 3442 135975 94345 100000 172971 86486 58356 56172 1 114785 1 77629 171869 25711 200000 68037 1 20964 175188 1 2900 142541 120723 60362 38651 95973 116555 100000 186567 93284 9329 191033 91851 100000 164273 82137 69295 1 19612 136758 6...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 304ms
memory: 76600kb
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:
175386 175386 170727 175386 175386 110841 175386 175386 76386 175386 175386 74708 175386 175386 126745 175386 175386 185798 175386 175386 27903 175386 175386 157263 175386 175386 151499 175386 175386 125962 175386 175386 135498 175386 175386 142371 175386 175386 48782 175386 175386 120715 175386 175...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 362ms
memory: 74580kb
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 23537 16791 163698 84168 139606 59302 45133 102212 129450 36071 66590 179652 10044 8498 121963 154803 72889 112576 103298 92023 149577 62393 52491 110120 36176 53316 130529 26773 72903 37916 196111 29472 143001 67960 158987 166223 109155 751...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 383ms
memory: 74632kb
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 81355 142861 110998 45021 101167 129885 15533 113720 195317 150042 173590 178458 23433 6693 186485 93168 84744 130124 16343 15187 47670 74142 25823 118876 105696 6646 116532 69796 185386 107065 117608 173194 102909 134958 151855 175566 95136 59440 76341 128223 ...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed