QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185514 | #4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》 | hos_lyric# | 50 | 1053ms | 455636kb | C++14 | 10.0kb | 2023-09-22 10:39:14 | 2024-07-04 02:06:40 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
struct Hld {
int n, rt;
// needs to be tree
// vertex lists
// modified in build(rt) (parent removed, heavy child first)
vector<vector<int>> graph;
vector<int> sz, par, dep;
int zeit;
vector<int> dis, fin, sid;
// head vertex (minimum depth) in heavy path
vector<int> head;
Hld() : n(0), rt(-1), zeit(0) {}
explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfsSz(int u) {
sz[u] = 1;
for (const int v : graph[u]) {
auto it = std::find(graph[v].begin(), graph[v].end(), u);
if (it != graph[v].end()) graph[v].erase(it);
par[v] = u;
dep[v] = dep[u] + 1;
dfsSz(v);
sz[u] += sz[v];
}
}
void dfsHld(int u) {
dis[u] = zeit++;
const int deg = graph[u].size();
if (deg > 0) {
int vm = graph[u][0];
int jm = 0;
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
if (sz[vm] < sz[v]) {
vm = v;
jm = j;
}
}
swap(graph[u][0], graph[u][jm]);
head[vm] = head[u];
dfsHld(vm);
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
head[v] = v;
dfsHld(v);
}
}
fin[u] = zeit;
}
void build(int rt_) {
assert(0 <= rt_); assert(rt_ < n);
rt = rt_;
sz.assign(n, 0);
par.assign(n, -1);
dep.assign(n, -1);
dep[rt] = 0;
dfsSz(rt);
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
head.assign(n, -1);
head[rt] = rt;
dfsHld(rt);
assert(zeit == n);
sid.assign(n, -1);
for (int u = 0; u < n; ++u) sid[dis[u]] = u;
}
friend ostream &operator<<(ostream &os, const Hld &hld) {
const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
vector<string> ss(2 * maxDep + 1);
int pos = 0, maxPos = 0;
for (int j = 0; j < hld.n; ++j) {
const int u = hld.sid[j];
const int d = hld.dep[u];
if (hld.head[u] == u) {
if (j != 0) {
pos = maxPos + 1;
ss[2 * d - 1].resize(pos, '-');
ss[2 * d - 1] += '+';
}
} else {
ss[2 * d - 1].resize(pos, ' ');
ss[2 * d - 1] += '|';
}
ss[2 * d].resize(pos, ' ');
ss[2 * d] += std::to_string(u);
if (maxPos < static_cast<int>(ss[2 * d].size())) {
maxPos = ss[2 * d].size();
}
}
for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
return os;
}
bool contains(int u, int v) const {
return (dis[u] <= dis[v] && dis[v] < fin[u]);
}
int lca(int u, int v) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
return (dis[u] > dis[v]) ? v : u;
}
int jumpUp(int u, int d) const {
assert(0 <= u); assert(u < n);
assert(d >= 0);
if (dep[u] < d) return -1;
const int tar = dep[u] - d;
for (u = head[u]; ; u = head[par[u]]) {
if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
}
}
int jump(int u, int v, int d) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(d >= 0);
const int l = lca(u, v);
const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
if (d <= du) {
return jumpUp(u, d);
} else if (d <= du + dv) {
return jumpUp(v, du + dv - d);
} else {
return -1;
}
}
// [u, v) or [u, v]
template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
assert(contains(v, u));
for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
if (inclusive) {
f(dis[v], dis[u] + 1);
} else {
if (v != u) f(dis[v] + 1, dis[u] + 1);
}
}
// not path order, include lca(u, v) or not
template <class F> void doPath(int u, int v, bool inclusive, F f) const {
const int l = lca(u, v);
doPathUp(u, l, false, f);
doPathUp(v, l, inclusive, f);
}
// (vs, ps): compressed tree
// vs: DFS order (sorted by dis)
// vs[ps[x]]: the parent of vs[x]
// ids[vs[x]] = x, not set for non-tree vertex
vector<int> ids;
pair<vector<int>, vector<int>> compress(vector<int> us) {
// O(n) first time
ids.resize(n, -1);
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
int usLen = us.size();
assert(usLen >= 1);
for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
usLen = us.size();
for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
vector<int> ps(usLen, -1);
for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
return make_pair(us, ps);
}
};
////////////////////////////////////////////////////////////////////////////////
constexpr int E = 62;
int N;
vector<int> A, B;
vector<Int> C;
int Q;
Hld hld;
int jss[E + 1][1'000'010];
void dfs(int e, int l, int r) {
if (e == 0) return;
if (l == r) return;
int pos = l;
for (int k = l; k < r; ++k) {
const int j = jss[e][k];
if (!(C[hld.sid[j]] >> (e-1) & 1)) jss[e-1][pos++] = j;
}
const int mid = pos;
dfs(e-1, l, mid);
for (int k = l; k < r; ++k) {
const int j = jss[e][k];
if (C[hld.sid[j]] >> (e-1) & 1) jss[e-1][pos++] = j;
}
dfs(e-1, mid, r);
}
void build() {
hld = Hld(N);
for (int i = 0; i < N - 1; ++i) {
hld.ae(A[i], B[i]);
}
hld.build(0);
// cerr<<hld<<endl;
for (int j = 0; j < N; ++j) {
jss[E][j] = j;
}
dfs(E, 0, N);
// for(int e=E;e>=0;--e){cerr<<"jss["<<e<<"] = ";pv(jss[e],jss[e]+N);}
}
Int query(int X, int Y, int M) {
// cerr<<COLOR("33")<<"query "<<X<<" "<<Y<<" "<<M<<COLOR()<<endl;
vector<pair<int, int>> ps;
hld.doPath(X, Y, true, [&](int jL, int jR) -> void {
ps.emplace_back(jL, jR);
});
// cerr<<"ps = "<<ps<<endl;
if (Q == 1) {
vector<Int> cs;
for (const auto &p : ps) {
for (int j = p.first; j < p.second; ++j) {
cs.push_back(C[hld.sid[j]]);
}
}
Int ans = 0;
for (int e = E; --e >= 0; ) {
ans |= 1LL << e;
int cnt = 0;
for (const Int c : cs) {
if (!(ans & ~c)) {
++cnt;
}
}
if (cnt < M) {
ans &= ~(1LL << e);
}
}
return ans;
}
vector<Int> cs;
Int ans = 0;
for (int e = E; --e >= 0; ) {
ans |= 1LL << e;
vector<Int> cRs;
if ([&]() -> bool {
int cnt = 0;
for (const Int c : cs) {
if (!(ans & ~c)) {
if (++cnt >= M) {
return true;
}
}
}
const Int tar = ans >> e;
for (const auto &p : ps) {
int lo = -1, hi = N;
for (; lo + 1 < hi; ) {
const int mid = (lo + hi) / 2;
const int j = jss[e][mid];
const Int c = C[hld.sid[j]];
((((c >> e) != tar) ? ((c >> e) > tar) : (j >= p.first)) ? hi : lo) = mid;
}
for (int pos = hi; pos < N; ++pos) {
const int j = jss[e][pos];
const Int c = C[hld.sid[j]];
if ((c >> e) == tar && j < p.second) {
assert(!(ans & ~c));
if (++cnt >= M) {
return true;
}
cRs.push_back(c);
} else {
break;
}
}
}
return false;
}()) {
// cerr<<"OK e = "<<e<<": cs = "<<cs<<endl;
vector<Int> ccs;
for (const Int c : cs) {
if (!(ans & ~c)) {
ccs.push_back(c);
}
}
cs = ccs;
} else {
ans &= ~(1LL << e);
cs.insert(cs.end(), cRs.begin(), cRs.end());
}
}
return ans;
}
int main() {
for (; ~scanf("%d", &N); ) {
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
C.resize(N);
for (int u = 0; u < N; ++u) {
scanf("%lld", &C[u]);
}
scanf("%d", &Q);
build();
Int lastans = 0;
for (int q = 0; q < Q; ++q) {
Int X, Y;
int M;
scanf("%lld%lld%d", &X, &Y, &M);
X = (X ^ lastans) % N + 1;
Y = (Y ^ lastans) % N + 1;
--X;
--Y;
assert(0 <= X); assert(X < N);
assert(0 <= Y); assert(Y < N);
const Int ans = query(X, Y, M);
printf("%lld\n", ans);
lastans = ans;
}
}
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 37168kb
input:
931 184 700 485 184 419 485 386 419 308 386 114 308 301 114 598 301 120 598 144 120 595 144 812 595 236 812 7 236 543 7 327 543 858 327 68 858 177 68 398 177 899 398 408 899 848 408 202 848 269 202 304 269 540 304 647 540 672 647 314 672 157 314 241 157 745 241 300 745 343 300 92 343 117 92 30 117 2...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #2:
score: 0
Accepted
time: 0ms
memory: 35080kb
input:
915 911 748 514 911 805 514 729 805 753 729 40 753 671 40 664 671 94 664 61 94 726 61 690 726 597 690 216 597 644 216 533 644 605 533 22 605 307 22 455 307 377 455 114 377 660 114 589 660 569 589 409 569 408 409 821 408 736 821 599 736 60 599 475 60 57 475 412 57 85 412 524 85 846 524 595 846 262 59...
output:
288230376151711752
result:
ok 1 number(s): "288230376151711752"
Test #3:
score: 0
Accepted
time: 0ms
memory: 35092kb
input:
930 111 896 637 111 559 637 289 559 103 289 759 103 341 759 605 341 778 605 154 778 169 154 721 169 631 721 741 631 750 741 344 750 641 344 639 641 769 639 48 769 389 48 25 389 70 25 508 70 185 508 199 185 602 199 89 602 473 89 565 473 373 565 865 373 867 865 658 867 271 658 685 271 269 685 317 269 ...
output:
268435456
result:
ok 1 number(s): "268435456"
Test #4:
score: 0
Accepted
time: 0ms
memory: 14976kb
input:
948 537 716 933 537 605 933 563 605 801 563 860 801 19 860 717 19 908 717 820 908 885 820 693 885 69 693 263 69 129 263 295 129 880 295 303 880 12 303 299 12 1 299 421 1 312 421 720 312 100 720 438 100 380 438 386 380 223 386 627 223 293 627 387 293 709 387 193 709 640 193 906 640 34 906 405 34 790 ...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4448kb
input:
928 626 381 247 626 97 247 358 97 886 358 898 886 736 898 776 736 75 776 123 75 512 123 223 512 355 223 530 355 95 530 523 95 903 523 144 903 324 144 382 324 487 382 127 487 538 127 171 538 836 171 129 836 259 129 914 259 574 914 7 574 141 7 246 141 65 246 482 65 865 482 265 865 690 265 925 690 449 ...
output:
134217728
result:
ok 1 number(s): "134217728"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4696kb
input:
941 87 448 396 87 398 396 623 398 837 623 234 837 896 234 258 896 700 258 52 700 27 52 515 27 308 515 774 308 76 774 21 76 753 21 493 753 902 493 878 902 58 878 146 58 342 146 414 342 312 414 621 312 88 621 460 88 683 460 150 683 845 150 535 845 467 535 326 467 247 326 280 247 474 280 124 474 22 124...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4776kb
input:
947 635 486 821 635 758 821 504 758 470 504 170 470 468 170 778 468 560 778 864 560 308 864 213 308 43 213 849 43 525 849 126 525 681 126 785 681 640 785 254 640 354 254 263 354 455 263 295 455 714 295 474 714 64 474 794 64 582 794 325 582 676 325 176 676 393 176 624 393 86 624 205 86 359 205 704 35...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #8:
score: 0
Accepted
time: 0ms
memory: 18808kb
input:
920 889 920 64 889 647 64 482 647 798 482 368 798 593 368 169 593 788 169 469 788 59 469 71 59 611 71 779 611 675 779 272 675 703 272 237 703 525 237 485 525 483 485 266 483 160 266 302 160 321 302 697 321 82 697 516 82 817 516 428 817 857 428 23 857 319 23 918 319 359 918 749 359 681 749 849 681 33...
output:
4398046511104
result:
ok 1 number(s): "4398046511104"
Subtask #2:
score: 5
Accepted
Dependency #1:
100%
Accepted
Test #9:
score: 5
Accepted
time: 441ms
memory: 17000kb
input:
949 158 116 73 158 131 73 252 131 596 252 9 596 488 9 555 488 828 555 150 828 388 150 586 388 903 586 24 903 405 24 746 405 321 746 48 321 588 48 431 588 225 431 299 225 325 299 593 325 516 593 829 516 369 829 775 369 90 775 610 90 45 610 793 45 745 793 859 745 422 859 342 422 91 342 773 91 32 773 4...
output:
4194304 2199023255552 288230376151711744 1152921504606846976 1152921504606846976 536870912 536870912 1152921504606846976 144115188075855872 576460752303423488 576460752303423488 2199023255552 2199023255552 1152921504606846976 128 1152921504606846976 1152921504606846976 0 70368744177664 0 11529215046...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 443ms
memory: 37156kb
input:
990 751 145 499 751 976 499 107 976 401 107 941 401 987 941 237 987 467 237 690 467 56 690 124 56 61 124 419 61 280 419 986 280 368 986 851 368 106 851 818 106 955 818 381 955 295 381 808 295 64 808 126 64 547 126 71 547 383 71 974 383 149 974 553 149 631 553 924 631 431 924 827 431 248 827 135 248 ...
output:
68719476736 18014398509481984 35184372088832 1125899906842624 1152921504606846976 64 1152921504606846976 1152921504606846976 0 18014398509481984 32768 549755813888 1152921504606846976 1125899906842624 1125899906842624 2199023255552 144115188075855872 72057594037927936 1152921504606846976 0 115292150...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 506ms
memory: 41460kb
input:
941 145 851 347 145 164 347 242 164 298 242 666 298 877 666 624 877 130 624 161 130 133 161 251 133 917 251 629 917 598 629 277 598 370 277 63 370 32 63 502 32 457 502 791 457 455 791 719 455 331 719 478 331 578 478 387 578 46 387 547 46 685 547 213 685 518 213 364 518 369 364 212 369 870 212 417 87...
output:
18014398509481984 144115188075855872 1152921504606846976 1048576 576460752303423488 18014398509481984 8 2199023255552 128 2251799813685248 1152921504606846976 1152921504606846976 144115188075855872 1152921504606846976 144115188075855872 8589934592 18014398509481984 0 1152921504606846976 115292150460...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 472ms
memory: 39092kb
input:
922 594 757 328 594 297 328 199 297 285 199 724 285 591 724 42 591 560 42 195 560 367 195 372 367 107 372 160 107 708 160 85 708 32 85 441 32 14 441 528 14 820 528 97 820 34 97 527 34 27 527 65 27 23 65 572 23 387 572 277 387 259 277 211 259 482 211 635 482 244 635 182 244 147 182 674 147 135 674 92...
output:
1152921504606846976 562949953421312 128 36028797018963968 1152921504606846976 274877906944 1152921504606846976 1073741824 72057594037927936 17179869184 144115188075855872 36028797018963968 576460752303423488 1073741824 1152921504606846976 2147483648 36028797018963968 576460752303423488 1152921504606...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 440ms
memory: 10612kb
input:
968 323 906 42 323 767 42 750 767 645 750 19 645 617 19 834 617 588 834 807 588 428 807 244 428 606 244 787 606 777 787 654 777 10 654 89 10 693 89 920 693 947 920 497 947 125 497 526 125 923 526 612 923 530 612 214 530 403 214 651 403 785 651 696 785 836 696 69 836 883 69 177 883 87 177 899 87 623 ...
output:
576460752303423488 18014398509481984 288230376151711744 0 36028797018963968 33554432 576460752303423488 549755813888 9007199254740992 576460752303423488 1152921504606846976 72057594037927936 576460752303423488 576460752303423488 1152921504606846976 288230376151711744 1152921504606846976 576460752303...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 458ms
memory: 12612kb
input:
933 158 663 512 158 109 512 226 109 704 226 799 704 492 799 796 492 836 796 439 836 76 439 497 76 544 497 30 544 5 30 592 5 294 592 186 294 140 186 103 140 659 103 426 659 421 426 343 421 253 343 413 253 106 413 92 106 281 92 562 281 884 562 487 884 69 487 664 69 214 664 757 214 169 757 21 169 204 2...
output:
0 72057594037927936 288230376151711744 144115188075855872 8192 288230376151711744 576460752303423488 72057594037927936 576460752303423488 72057594037927936 1152921504606846976 68719476736 1152921504606846976 1152921504606846976 35184372088832 34359738368 562949953421312 576460752303423488 8192 87960...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 486ms
memory: 4444kb
input:
901 438 539 372 438 163 372 673 163 559 673 595 559 478 595 830 478 832 830 883 832 506 883 665 506 861 665 119 861 555 119 76 555 220 76 751 220 113 751 72 113 196 72 834 196 228 834 354 228 491 354 893 491 529 893 212 529 150 212 53 150 746 53 85 746 796 85 583 796 530 583 393 530 467 393 459 467 ...
output:
576460752303423488 36028797018963968 0 1152921504606846976 36028797018963968 0 9007199254740992 72057594037927936 2199023255552 576460752303423488 144115188075855872 1152921504606846976 4096 35184372088832 1152921504606846976 35184372088832 1152921504606846976 1152921504606846976 2199023255552 11529...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 473ms
memory: 4728kb
input:
905 587 47 409 587 793 409 100 793 637 100 274 637 247 274 530 247 229 530 893 229 585 893 617 585 653 617 832 653 414 832 374 414 784 374 772 784 458 772 780 458 613 780 870 613 766 870 115 766 760 115 300 760 890 300 830 890 819 830 873 819 535 873 520 535 444 520 208 444 433 208 717 433 66 717 59...
output:
9007199254740992 72057594037927936 0 4398046511104 1152921504606846976 16384 1152921504606846976 72057594037927936 72057594037927936 1152921504606846976 281474976710656 1152921504606846976 72057594037927936 1152921504606846976 9007199254740992 9007199254740992 281474976710656 576460752303423488 1152...
result:
ok 100000 numbers
Subtask #3:
score: 10
Accepted
Test #17:
score: 10
Accepted
time: 46ms
memory: 46568kb
input:
99115 98506 98914 1961 98506 45808 1961 23027 45808 16655 23027 66393 16655 77250 66393 68284 77250 53684 68284 21189 53684 84955 21189 73464 84955 47574 73464 40651 47574 21101 40651 6589 21101 59680 6589 6185 59680 25529 6185 207 25529 33286 207 98459 33286 92565 98459 85446 92565 97388 85446 1630...
output:
2050
result:
ok 1 number(s): "2050"
Test #18:
score: 0
Accepted
time: 53ms
memory: 77004kb
input:
99546 79711 12863 50539 79711 13393 50539 27933 13393 13465 27933 79157 13465 53742 79157 51081 53742 32220 51081 21079 32220 85595 21079 50222 85595 14565 50222 4589 14565 13763 4589 58913 13763 93835 58913 34953 93835 2185 34953 10246 2185 64420 10246 44274 64420 63093 44274 8007 63093 85947 8007 ...
output:
512
result:
ok 1 number(s): "512"
Test #19:
score: 0
Accepted
time: 59ms
memory: 77796kb
input:
99762 90013 76047 42293 90013 7801 42293 75274 7801 59320 75274 60896 59320 10435 60896 5384 10435 34648 5384 15596 34648 92041 15596 67457 92041 20760 67457 65611 20760 81462 65611 38984 81462 17583 38984 83787 17583 59980 83787 71477 59980 31143 71477 92168 31143 71205 92168 69348 71205 6111 69348...
output:
16386
result:
ok 1 number(s): "16386"
Test #20:
score: 0
Accepted
time: 41ms
memory: 73092kb
input:
99132 46469 40521 51811 46469 47968 51811 10584 47968 73 10584 27351 73 16693 27351 12495 16693 53425 12495 95973 53425 24901 95973 82771 24901 49155 82771 35995 49155 50432 35995 91209 50432 5781 91209 83457 5781 41361 83457 37973 41361 48829 37973 62896 48829 77593 62896 21307 77593 86547 21307 61...
output:
8194
result:
ok 1 number(s): "8194"
Test #21:
score: 0
Accepted
time: 42ms
memory: 73356kb
input:
99403 81802 91324 60321 81802 76749 60321 70097 76749 16085 70097 8301 16085 61886 8301 72994 61886 23906 72994 18815 23906 6781 18815 7774 6781 18318 7774 54769 18318 39330 54769 55677 39330 46758 55677 36164 46758 10159 36164 24678 10159 29603 24678 14941 29603 7966 14941 42934 7966 35909 42934 24...
output:
32770
result:
ok 1 number(s): "32770"
Test #22:
score: 0
Accepted
time: 39ms
memory: 71660kb
input:
99468 33859 68644 12306 33859 44304 12306 18200 44304 27325 18200 35907 27325 88149 35907 71599 88149 86384 71599 83793 86384 19513 83793 4843 19513 3007 4843 52878 3007 83019 52878 5275 83019 61517 5275 21453 61517 55993 21453 50710 55993 16211 50710 76061 16211 12048 76061 41970 12048 86181 41970 ...
output:
514
result:
ok 1 number(s): "514"
Test #23:
score: 0
Accepted
time: 47ms
memory: 73428kb
input:
99179 45430 91876 8718 45430 75718 8718 15306 75718 21806 15306 78221 21806 74287 78221 66218 74287 66830 66218 64948 66830 16118 64948 33879 16118 81821 33879 69640 81821 27802 69640 25979 27802 6393 25979 63447 6393 48459 63447 53612 48459 27525 53612 52654 27525 80810 52654 767 80810 23808 767 82...
output:
32768
result:
ok 1 number(s): "32768"
Test #24:
score: 0
Accepted
time: 55ms
memory: 72040kb
input:
99240 8561 98467 49571 8561 13264 49571 94195 13264 85879 94195 53012 85879 29828 53012 25813 29828 57793 25813 10678 57793 88525 10678 70070 88525 54163 70070 51466 54163 3857 51466 77958 3857 29023 77958 154 29023 5173 154 4349 5173 24310 4349 21821 24310 36125 21821 75498 36125 7147 75498 22336 7...
output:
32770
result:
ok 1 number(s): "32770"
Subtask #4:
score: 5
Accepted
Dependency #1:
100%
Accepted
Dependency #3:
100%
Accepted
Test #25:
score: 5
Accepted
time: 1053ms
memory: 431480kb
input:
992362 488995 967308 576776 488995 440373 576776 199494 440373 436524 199494 260014 436524 157103 260014 693611 157103 218612 693611 590935 218612 701779 590935 112004 701779 322594 112004 53706 322594 442686 53706 659639 442686 567880 659639 786210 567880 289019 786210 599273 289019 188834 599273 1...
output:
1152921504606846984
result:
ok 1 number(s): "1152921504606846984"
Test #26:
score: 0
Accepted
time: 931ms
memory: 410144kb
input:
992770 411251 413303 421801 411251 751171 421801 294667 751171 506990 294667 136648 506990 288093 136648 514687 288093 886681 514687 75611 886681 178157 75611 99736 178157 277007 99736 744383 277007 226929 744383 53879 226929 617778 53879 170759 617778 467641 170759 123171 467641 732929 123171 90501...
output:
1152921504606847232
result:
ok 1 number(s): "1152921504606847232"
Test #27:
score: 0
Accepted
time: 899ms
memory: 413112kb
input:
992506 78169 990749 904956 78169 8556 904956 618930 8556 318854 618930 643267 318854 255067 643267 635064 255067 911717 635064 932598 911717 323834 932598 620573 323834 172635 620573 541580 172635 96011 541580 745144 96011 403925 745144 60605 403925 118756 60605 219373 118756 253153 219373 30380 253...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #28:
score: 0
Accepted
time: 991ms
memory: 455636kb
input:
998381 898343 893428 759432 898343 531529 759432 497678 531529 960345 497678 211399 960345 268908 211399 804788 268908 48879 804788 567713 48879 934755 567713 587571 934755 2755 587571 357711 2755 312979 357711 758254 312979 494581 758254 906640 494581 80127 906640 558475 80127 694426 558475 34296 6...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Subtask #5:
score: 10
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #29:
score: 10
Accepted
time: 127ms
memory: 82804kb
input:
99226 5279 56171 56708 5279 93918 56708 46612 93918 92631 46612 23135 92631 10349 23135 53057 10349 56629 53057 54566 56629 2518 54566 39322 2518 2240 39322 31992 2240 97583 31992 68136 97583 69869 68136 37827 69869 1210 37827 50065 1210 6617 50065 57500 6617 57892 57500 89598 57892 10109 89598 8431...
output:
1152921504606846976 1152921504606846984 1152921504606846984 1152921504606846976 281474976710656 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 274877906944 1152921504606846976 1152921504606846976 144115188075855874 115292150460...
result:
ok 9965 numbers
Test #30:
score: 0
Accepted
time: 109ms
memory: 84672kb
input:
99131 86117 49115 12523 86117 18106 12523 31418 18106 61736 31418 77297 61736 37409 77297 21866 37409 73758 21866 33590 73758 8327 33590 47474 8327 78931 47474 63290 78931 407 63290 84058 407 8558 84058 6242 8558 89267 6242 42248 89267 34160 42248 3134 34160 6579 3134 7405 6579 47360 7405 46220 4736...
output:
1152921504606846976 72057594037927936 1152921504606846978 1152921504606846976 17592186044416 1152921504606846976 524288 1152921504606846976 4194304 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 576460752303423488 1152921504606846976 1441151880758...
result:
ok 9909 numbers
Test #31:
score: 0
Accepted
time: 123ms
memory: 78608kb
input:
99615 95650 89972 29012 95650 19894 29012 77233 19894 14383 77233 87222 14383 85565 87222 61993 85565 71297 61993 73788 71297 8626 73788 67633 8626 1885 67633 65599 1885 10040 65599 31321 10040 55933 31321 28063 55933 56351 28063 40756 56351 42362 40756 28551 42362 47749 28551 48770 47749 40567 4877...
output:
262144 1152921504606846976 576460752303423488 1152921504606846976 1152921504606846976 576460752303423488 1152921504606846992 1152921504606846976 36028797018963968 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 11529215046068469...
result:
ok 9947 numbers
Test #32:
score: 0
Accepted
time: 116ms
memory: 85056kb
input:
99501 54076 23445 75253 54076 64548 75253 89989 64548 50278 89989 90578 50278 12194 90578 9923 12194 35987 9923 41698 35987 1578 41698 41232 1578 378 41232 95959 378 80008 95959 22021 80008 71293 22021 32789 71293 84262 32789 36733 84262 58067 36733 30161 58067 43171 30161 47202 43171 1689 47202 753...
output:
1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1048576 1152921504606846976 576460752303423488 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606...
result:
ok 9933 numbers
Test #33:
score: 0
Accepted
time: 115ms
memory: 79760kb
input:
99293 50859 98730 98591 50859 32948 98591 80691 32948 9920 80691 27594 9920 84857 27594 25772 84857 14792 25772 14973 14792 71451 14973 55376 71451 33920 55376 93689 33920 44355 93689 18986 44355 58274 18986 51746 58274 75969 51746 81440 75969 91096 81440 24271 91096 2460 24271 83026 2460 71901 8302...
output:
18014398509481984 1152921504606846976 1152921504606846980 140737488355328 1152921504606846980 1152921504606846976 1152921504606846976 562949953421312 18014398509481984 1152921504606846976 9007199254740992 1152921504606846976 1152921504606846976 16777216 1152921504606846976 1152921504606846976 288230...
result:
ok 9960 numbers
Test #34:
score: 0
Accepted
time: 123ms
memory: 72992kb
input:
99870 41281 68626 3628 41281 3207 3628 85989 3207 70200 85989 4817 70200 18845 4817 50730 18845 4026 50730 42926 4026 78127 42926 70770 78127 55171 70770 552 55171 59073 552 11064 59073 25328 11064 87894 25328 7477 87894 22659 7477 28619 22659 37254 28619 86444 37254 6889 86444 50846 6889 55534 5084...
output:
1152921504606846978 1152921504606846976 1152921504606846978 1073741824 1152921504606846976 1152921504606846976 1152921504606846976 576460752303423488 1152921504606846976 1152921504606846976 1152921504606846976 1152921504606846976 576460752303423488 2147483648 1152921504606846976 1152921504606846976 ...
result:
ok 9928 numbers
Test #35:
score: 0
Accepted
time: 125ms
memory: 74376kb
input:
99141 35571 77107 36738 35571 94150 36738 56455 94150 86575 56455 99060 86575 32548 99060 5443 32548 22637 5443 37290 22637 10646 37290 90761 10646 55035 90761 37297 55035 46976 37297 37918 46976 72075 37918 78292 72075 53160 78292 77446 53160 16425 77446 13001 16425 66243 13001 39211 66243 15168 39...
output:
1152921504606846976 1152921504606846976 36028797018963968 1152921504606846976 1152921504606846976 512 1152921504606846976 137438953472 18014398509481984 1152921504606846976 72057594037927936 1152921504606846976 1152921504606846976 2199023255552 72057594037927936 72057594037927936 562949953421312 576...
result:
ok 9996 numbers
Test #36:
score: 0
Accepted
time: 106ms
memory: 77936kb
input:
99022 97091 76784 39255 97091 95281 39255 34487 95281 94367 34487 1575 94367 84183 1575 33838 84183 39271 33838 78809 39271 21521 78809 25277 21521 78537 25277 96267 78537 25696 96267 88635 25696 41012 88635 39376 41012 93351 39376 29213 93351 36277 29213 15302 36277 29206 15302 44983 29206 69989 44...
output:
1152921504606846976 1152921504606846976 4503599627370496 1152921504606846976 1152921504606879744 1152921504606879744 1152921504606846976 1152921504606846976 1152921504606846976 1125899906842624 1152921504606847040 1152921504606846976 35184372088832 1152921504606846976 1152921504606846976 11258999068...
result:
ok 9959 numbers
Subtask #6:
score: 15
Accepted
Dependency #5:
100%
Accepted
Test #37:
score: 15
Accepted
time: 347ms
memory: 74084kb
input:
99703 27900 98506 73621 98506 65967 98506 99084 98506 64267 98506 56800 98506 37555 98506 71856 98506 70274 98506 92346 65967 54463 98506 49909 98506 36645 92346 74593 54463 6270 98506 30425 74593 26211 98506 5099 98506 50305 30425 44107 98506 57865 36645 41363 70274 18689 36645 7422 73621 16591 503...
output:
536870912 562949953421312 32768 2048 8192 18014398509481984 268435456 8 68719476736 4398046511104 2 576460752303423488 18014398509481984 1024 536870912 549755813888 8388608 134217728 144115188075855872 128 268435456 140737488355328 4398046511104 4 1073741824 2097152 18014398509481984 900719925474099...
result:
ok 9907 numbers
Test #38:
score: 0
Accepted
time: 327ms
memory: 68128kb
input:
99932 43560 3726 51011 43560 74749 51011 80900 3726 79242 80900 22947 74749 24282 3726 24468 22947 73971 51011 62733 22947 65271 3726 86759 22947 38411 74749 36727 24468 21505 22947 82990 51011 60505 86759 90448 43560 29157 73971 67618 22947 91883 74749 58638 79242 31978 51011 49121 24468 21121 2915...
output:
262144 134217728 8589934592 16777216 67108864 16777216 134217728 1073741824 8 18014398509481984 134217728 32768 134217728 134217728 8589934592 137438953472 65536 8589934592 18014398509481984 1024 18014398509481984 137438953472 16777216 8192 8589934592 524288 1073741824 18014398509481984 180143985094...
result:
ok 9994 numbers
Test #39:
score: 0
Accepted
time: 320ms
memory: 71468kb
input:
99782 55146 78372 8134 78372 84051 78372 54282 78372 55921 78372 45845 78372 66967 78372 8750 78372 27237 78372 11677 78372 53352 78372 96197 78372 41543 78372 68196 78372 24324 8134 63730 78372 88022 78372 76165 41543 6771 78372 15970 55146 98523 78372 64562 55146 30421 78372 25803 78372 28270 6456...
output:
34359738368 2251799813685248 137438953472 137438953472 1073741824 576460752303423488 4294967296 64 137438953472 137438953472 576460752303423488 0 8192 576460752303423488 4096 576460752303423488 524288 576460752303423488 33554432 2097152 8192 137438953472 1073741824 131072 16777216 1073741824 16 1374...
result:
ok 9902 numbers
Test #40:
score: 0
Accepted
time: 351ms
memory: 66492kb
input:
99958 75201 37320 9692 37320 10807 37320 14157 37320 82391 37320 37761 37320 7406 37320 62164 37320 93034 37320 48603 37320 10109 37320 23985 82391 98999 82391 55282 37320 91441 37320 50305 37320 6235 37320 50000 98999 14786 37320 59396 23985 21058 37320 61759 50000 75630 50000 58957 61759 91725 752...
output:
9007199254740992 512 2199023255552 2 536870912 65536 137438953472 4096 16384 33554432 262144 524288 536870912 72057594037927936 8 576460752303423488 536870912 1099511627776 536870912 536870912 34359738368 9007199254740992 1099511627776 524288 140737488355328 16384 70368744177664 2199023255552 140737...
result:
ok 9947 numbers
Test #41:
score: 0
Accepted
time: 356ms
memory: 70452kb
input:
99490 25639 26126 55163 26126 68405 26126 43121 26126 76625 26126 4490 26126 92431 26126 1968 26126 6078 26126 93767 26126 12470 26126 58025 26126 98269 92431 21669 25639 55010 1968 33104 26126 13201 98269 10577 26126 62359 26126 67473 55010 20637 13201 75341 13201 47597 13201 12821 26126 77928 1320...
output:
68719476736 256 8796093022208 16 1048576 1152921504606846976 274877906944 68719476736 4194304 8 274877906944 274877906944 16 137438953472 262144 8388608 4194304 2147483648 35184372088832 2147483648 288230376151711744 4194304 4096 1152921504606846976 8388608 524288 2147483648 1152921504606846976 6871...
result:
ok 9952 numbers
Test #42:
score: 0
Accepted
time: 326ms
memory: 72436kb
input:
99207 17783 95040 84551 95040 81241 95040 9621 95040 91183 95040 6319 95040 11497 95040 74083 95040 94250 95040 29861 95040 17050 95040 33286 95040 90508 95040 20782 95040 82486 95040 57412 95040 66783 95040 77936 95040 92863 17783 67985 95040 74668 95040 50306 57412 84449 95040 11096 95040 33392 95...
output:
8388608 268435456 72057594037927936 268435456 4398046511104 0 18014398509481984 8388608 34359738368 4398046511104 131072 4096 64 8388608 4194304 1048576 18014398509481984 281474976710656 72057594037927936 16384 72057594037927936 33554432 34359738368 8388608 18014398509481984 17592186044416 1048576 4...
result:
ok 9910 numbers
Test #43:
score: 0
Accepted
time: 351ms
memory: 69332kb
input:
99962 8418 48533 43838 48533 45127 48533 32976 48533 13465 45127 98430 8418 4583 48533 12701 48533 87334 48533 91109 4583 77403 48533 86629 48533 42208 48533 99557 48533 801 48533 45638 48533 11189 45127 18142 48533 76993 91109 11658 86629 28482 48533 74164 42208 57107 48533 60092 48533 95867 99557 ...
output:
288230376151711744 144115188075855872 576460752303423488 2199023255552 549755813888 1048576 8388608 144115188075855872 536870912 131072 576460752303423488 576460752303423488 576460752303423488 34359738368 512 549755813888 576460752303423488 128 549755813888 0 549755813888 524288 288230376151711744 1...
result:
ok 9905 numbers
Test #44:
score: 0
Accepted
time: 342ms
memory: 69404kb
input:
99625 25315 86141 74751 86141 89028 86141 97585 86141 73523 86141 65649 25315 15981 86141 36679 86141 78866 86141 50917 25315 64912 86141 99535 86141 12991 86141 15354 65649 17947 97585 13613 25315 24775 15354 7852 73523 1166 24775 8798 89028 40176 89028 34310 24775 36138 64912 36596 36138 32512 975...
output:
281474976710656 33554432 281474976710656 18014398509481984 2048 34359738368 8589934592 128 128 256 281474976710656 8192 256 8589934592 281474976710656 18014398509481984 18014398509481984 256 18014398509481984 8192 32768 2048 512 2 33554432 262144 268435456 8388608 33554432 33554432 18014398509481984...
result:
ok 9931 numbers
Subtask #7:
score: 0
Time Limit Exceeded
Test #45:
score: 0
Time Limit Exceeded
input:
996678 2 1 3 1 4 1 5 1 6 3 7 5 8 5 9 5 10 7 11 8 12 9 13 1 14 2 15 7 16 4 17 5 18 17 19 16 20 2 21 1 22 1 23 9 24 17 25 19 26 10 27 9 28 7 29 25 30 25 31 4 32 11 33 31 34 21 35 13 36 19 37 25 38 10 39 11 40 20 41 35 42 1 43 19 44 20 45 41 46 1 47 19 48 5 49 28 50 21 51 33 52 7 53 14 54 21 55 20 56 1...
output:
4 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 8 0 0 0 0 16 0 0 4096 0 0 0 0 4096 0 0 0 0 2 0 0 0 0 4 0 0 0 0 32 64 0 0 0 512 64 4 4096 0 2 0 0 131072 0 0 0 0 0 0 0 0 2 0 0 0 2 0 4096 2 0 0 0 0 0 512 2 8 0 0 4096 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 512 0 0 36 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
0%