QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201034 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | hos_lyric# | 31 | 801ms | 98132kb | C++14 | 13.4kb | 2023-10-05 07:26:54 | 2024-07-04 02:16:13 |
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);
}
};
////////////////////////////////////////////////////////////////////////////////
int N;
vector<int> A, B;
int Q;
vector<int> X, Y, D;
vector<vector<int>> graph;
Hld hld;
namespace brute {
vector<int> run() {
cerr<<"[brute::run]"<<endl;
vector<int> ans(Q, 0);
for (int q = 0; q < Q; ++q) {
const int x = X[q], y = Y[q];
const int l = hld.lca(x, y);
queue<int> que;
vector<int> dist(N, -1);
auto reach = [&](int v, int c) -> void {
if (!~dist[v]) {
dist[v] = c;
que.push(v);
}
};
for (int u = x; u != l; u = hld.par[u]) reach(u, 0);
for (int u = y; u != l; u = hld.par[u]) reach(u, 0);
reach(l, 0);
for (; !que.empty(); ) {
const int u = que.front();
que.pop();
for (const int v : graph[u]) reach(v, dist[u] + 1);
}
for (int u = 0; u < N; ++u) if (dist[u] <= D[q]) {
++ans[q];
}
}
return ans;
}
} // brute
namespace sub3 {
vector<vector<pair<int, pair<int, int>>>> ess;
vector<int> ans;
vector<int> sz, del;
void dfsSz(int u, int p) {
sz[u] = 1;
for (const int v : graph[u]) if (p != v) {
dfsSz(v, u);
sz[u] += sz[v];
}
}
string dfsString(int u, int p) {
ostringstream oss;
oss << "[" << u;
for (const int v : graph[u]) if (!del[v] && p != v) {
oss << " " << dfsString(v, u);
}
oss << "]";
return oss.str();
}
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vector<int> par, dep;
vector<vector<int>> uss, fss;
void dfs(int j, int u, int p, int d) {
par[u] = p;
dep[u] = d;
uss[j].push_back(u);
if ((int)fss[j].size() < d + 1) fss[j].resize(d + 1, 0);
++fss[j][d];
for (const int v : graph[u]) if (!del[v] && p != v) {
dfs(j, v, u, d + 1);
}
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void solveSubtree(int depth, int r) {
#ifdef LOCAL
cerr << string(2 * depth, ' ') << "solveSubtree " << dfsString(r, -1) << endl;
#endif
vector<int> vs;
for (const int v : graph[r]) if (!del[v]) {
vs.push_back(v);
}
const int len = vs.size();
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
sort(vs.begin(), vs.end());
uss.assign(len, {});
fss.assign(len + 1, vector<int>(2, 0));
for (int j = 0; j < len; ++j) {
dfs(j, vs[j], r, 1);
}
int mx = 2;
for (int j = 0; j < len; ++j) {
chmax(mx, (int)fss[j].size());
}
fss[len].assign(mx, 0);
par[r] = -1;
dep[r] = 0;
++fss[len][0];
for (int j = 0; j < len; ++j) {
for (int d = 0; d < (int)fss[j].size(); ++d) {
fss[len][d] += fss[j][d];
}
}
for (int j = 0; j <= len; ++j) {
for (int d = 1; d < (int)fss[j].size(); ++d) {
fss[j][d] += fss[j][d - 1];
}
}
// cerr<<string(2*depth,' ')<<"uss = "<<uss<<", fss = "<<fss<<endl;
auto get = [&](int j, int d) -> int {
return fss[j][min(d, (int)fss[j].size() - 1)];
};
for (const auto &e : ess[r]) {
const int q = e.first;
ans[q] += get(len, D[q]);
for (const int v : {e.second.first, e.second.second}) {
const int j = lower_bound(vs.begin(), vs.end(), v) - vs.begin();
if (j < len && vs[j] == v) {
ans[q] -= get(j, D[q]);
}
}
}
for (int j = 0; j < len; ++j) {
for (const int u : uss[j]) {
for (const auto &e : ess[u]) {
const int q = e.first;
if (par[u] != e.second.first && par[u] != e.second.second && dep[u] <= D[q]) {
ans[q] += get(len, D[q] - dep[u]);
ans[q] -= get(j, D[q] - dep[u]);
}
}
}
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
void solveRec(int depth, int u) {
for (; ; ) {
int vm = -1;
for (const int v : graph[u]) if (!del[v]) {
if (!~vm || sz[vm] < sz[v]) {
vm = v;
}
}
if (!~vm || 2 * sz[vm] <= sz[u]) {
solveSubtree(depth, u);
del[u] = 1;
for (const int v : graph[u]) if (!del[v]) {
solveRec(depth + 1, v);
}
break;
} else {
sz[u] -= sz[vm];
sz[vm] += sz[u];
u = vm;
}
}
}
void centroidDecomp() {
sz.assign(N, 0);
dfsSz(0, -1);
del.assign(N, 0);
par.resize(N);
dep.resize(N);
solveRec(0, 0);
}
vector<int> run() {
cerr<<"[sub3::run]"<<endl;
ess.assign(N, {});
for (int q = 0; q < Q; ++q) {
const int x = X[q], y = Y[q];
const int l = hld.lca(x, y);
vector<int> us, vs;
for (int u = x; u != l; u = hld.par[u]) us.push_back(u);
us.push_back(l);
for (int u = y; u != l; u = hld.par[u]) vs.push_back(u);
reverse(vs.begin(), vs.end());
us.insert(us.end(), vs.begin(), vs.end());
const int usLen = us.size();
// cerr<<us<<endl;
for (int j = 0; j < usLen; ++j) {
const int uL = (j - 1 >= 0) ? us[j - 1] : -1;
const int u = us[j];
const int uR = (j + 1 < usLen) ? us[j + 1] : -1;
ess[u].emplace_back(q, make_pair(uL, uR));
}
}
ans.assign(Q, 0);
centroidDecomp();
return ans;
}
} // sub3
namespace sub4 {
vector<vector<int>> jss;
int calc(int u, int d) {
if (d >= N) return 0;
const auto &js = jss[d];
const int posDis = lower_bound(js.begin(), js.end(), hld.dis[u]) - js.begin();
const int posFin = lower_bound(js.begin(), js.end(), hld.fin[u]) - js.begin();
return posFin - posDis;
}
vector<int> run() {
cerr<<"[sub4::run]"<<endl;
jss.assign(N, {});
for (int j = 0; j < N; ++j) {
jss[hld.dep[hld.sid[j]]].push_back(j);
}
vector<int> ans(Q, 0);
for (int q = 0; q < Q; ++q) {
const int x = X[q], y = Y[q];
const int l = hld.lca(x, y);
for (int u = x; u != l; u = hld.par[u]) ans[q] += calc(u, hld.dep[u] + D[q]);
for (int u = y; u != l; u = hld.par[u]) ans[q] += calc(u, hld.dep[u] + D[q]);
ans[q] += calc(l, hld.dep[l] + D[q]);
{
int d = hld.dep[l];
int u = l;
for (int k = D[q]; --k >= 0; ) {
ans[q] += calc(u, d + k);
--d;
u = hld.par[u];
if (!~u) u = 0;
ans[q] += calc(u, d + k);
}
}
}
return ans;
}
} // sub4
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];
}
scanf("%d", &Q);
X.resize(Q);
Y.resize(Q);
D.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%d%d%d", &X[q], &Y[q], &D[q]);
--X[q];
--Y[q];
}
graph.assign(N, {});
hld = Hld(N);
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
hld.ae(A[i], B[i]);
}
hld.build(0);
const int maxD = *max_element(D.begin(), D.end());
vector<int> ans;
if (maxD <= 20) {
ans = sub4::run();
} else if (N <= 5000 && Q <= 5000) {
ans = brute::run();
} else {
ans = sub3::run();
}
for (int q = 0; q < Q; ++q) {
printf("%d\n", ans[q]);
}
}
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
result:
Subtask #2:
score: 8
Accepted
Test #9:
score: 8
Accepted
time: 360ms
memory: 49792kb
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
757 69428 2793 181264 91707 182 32496 199183 6399 15975 11640 119051 236 689 15 9532 41 36592 178936 56 45424 193403 90248 3417 949 68 34133 60471 199861 188090 75088 127 1 6 4 3 3 11 61157 199860 199153 155706 196287 192862 53742 51862 179199 428 196282 199989 3613 26 99007 134461 198159 20382 7518...
result:
ok 199996 numbers
Test #10:
score: 0
Accepted
time: 205ms
memory: 49584kb
input:
199993 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
22 31743 62 30 510 6079 94 24063 190 4079 382 30 62 12159 1022 2043 8063 62 4 3063 4079 30 254 46 10 22 6111 12159 16127 22 1 12031 1 94 382 766 4063 254 46 766 1022 62 766 1 22 46 30 8063 8063 254 3063 22 62 30 1 62 254 4 10 15871 1022 46 2039 6079 22 254 1022 16127 30 766 8127 14 14 10 46 1 62 406...
result:
ok 199995 numbers
Test #11:
score: 0
Accepted
time: 431ms
memory: 56656kb
input:
199993 25163 125238 125238 19096 19096 88864 88864 113505 113505 12722 12722 56225 56225 8736 8736 74926 74926 38529 38529 80231 80231 19719 19719 198784 198784 75213 75213 190174 190174 163340 163340 62363 62363 144160 144160 130912 130912 3919 3919 21218 21218 85281 85281 187312 187312 79930 79930...
output:
97095 57496 116181 132482 144412 69917 174677 96334 37980 80902 148979 22074 166530 153392 43419 163281 148526 62703 79363 199993 153733 152298 5085 156125 117973 61925 36346 95741 124148 102890 20093 5408 77598 176994 177809 169850 144418 43786 189237 69098 5167 199993 103575 105198 197612 38829 20...
result:
ok 199994 numbers
Test #12:
score: 0
Accepted
time: 528ms
memory: 69020kb
input:
200000 3219 118490 118490 61372 61372 74390 74390 88375 88375 63918 63918 37580 37580 33219 33219 170480 170480 81737 81737 153202 153202 93921 93921 149109 149109 88339 88339 167037 167037 67099 67099 58363 58363 6784 6784 109386 109386 11895 11895 14872 14872 65638 65638 43958 43958 181669 181669 ...
output:
59633 108235 72863 144596 90365 57521 48069 163045 124462 18633 39115 111210 59413 80420 86945 182373 99188 57011 148702 53778 132289 68037 69705 50797 91155 77852 27499 106082 87174 122445 78221 71755 10125 93101 163451 16175 104215 50130 81182 30091 44299 81429 91045 111890 73099 72278 74017 59177...
result:
ok 199992 numbers
Test #13:
score: 0
Accepted
time: 271ms
memory: 53364kb
input:
199992 1 2 1 3 2 4 2 5 4 6 1 7 5 8 5 9 3 10 6 11 4 12 4 13 6 14 5 15 9 16 11 17 17 18 13 19 18 20 14 21 18 22 17 23 21 24 19 25 25 26 25 27 27 28 21 29 20 30 29 31 23 32 31 33 33 34 34 35 28 36 33 37 28 38 38 39 30 40 33 41 33 42 38 43 41 44 44 45 44 46 41 47 45 48 41 49 47 50 49 51 42 52 50 53 44 5...
output:
40732 40074 40815 13444 89657 22422 23494 61358 102922 66209 62228 32272 77095 68562 27799 74336 45129 71632 68525 13022 71347 63735 92178 64200 90446 50728 83632 61441 43695 10496 35481 81587 75266 77943 56182 14188 46302 108160 84166 3192 52959 522 57676 28165 97982 15371 95012 3437 53633 49240 55...
result:
ok 199998 numbers
Test #14:
score: 0
Accepted
time: 241ms
memory: 61236kb
input:
199990 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50...
output:
59224 71441 128293 104009 42824 136779 12532 93560 81095 108628 176617 63487 103752 175849 36193 178489 73311 34313 46423 75989 76344 145231 20076 127399 81148 17356 39455 99025 44904 3548 78503 135455 28 136931 58140 53161 33288 134084 67877 26048 51868 74301 139992 165315 126781 136117 28112 86333...
result:
ok 199996 numbers
Test #15:
score: 0
Accepted
time: 197ms
memory: 49432kb
input:
199997 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:
65710 203 400 304 388 328 441 19 417 49 311 329 193 71968 895 179 152645 282 7600 185 150933 150045 444 3693 56770 34420 8765 335 73751 4665 3 203 380 44479 392 356 113 373 46663 143312 234 265 386 378 339 184360 404 21904 9861 393 445 441 91 299 9 213 24586 65263 22235 121 35761 169 36121 435 40035...
result:
ok 199995 numbers
Test #16:
score: 0
Accepted
time: 468ms
memory: 49048kb
input:
199997 1 64008 2 4187 3 154904 4 191579 5 107782 6 29053 7 123085 8 191601 9 95335 10 164039 11 171804 12 145532 13 104884 14 19820 15 74055 16 14172 17 98802 18 144668 19 188276 20 173096 21 62815 22 133749 23 65035 24 161785 25 191028 26 84730 27 176488 28 173295 29 110316 30 121532 31 81037 32 81...
output:
135622 123942 47301 113894 93180 10469 9237 13166 2896 20323 182669 26483 168662 47202 7900 7785 129591 1577 17943 5638 16670 16980 32760 153668 394 142656 30298 1801 167880 25099 10860 39103 28660 158337 55 126816 57661 17387 11147 95051 3 13130 28040 163801 141 109445 110915 13173 56634 20527 6325...
result:
ok 199993 numbers
Subtask #3:
score: 23
Accepted
Dependency #2:
100%
Accepted
Test #17:
score: 23
Accepted
time: 495ms
memory: 59852kb
input:
199996 1 2 2 3 3 4 1 5 1 6 4 7 1 8 5 9 4 10 4 11 7 12 11 13 7 14 10 15 2 16 1 17 9 18 10 19 9 20 13 21 8 22 14 23 21 24 8 25 20 26 23 27 17 28 6 29 9 30 9 31 14 32 14 33 6 34 7 35 35 36 31 37 37 38 2 39 12 40 16 41 18 42 3 43 27 44 4 45 7 46 24 47 16 48 44 49 10 50 11 51 9 52 16 53 39 54 30 55 4 56 ...
output:
190330 676 6 462 40 5 180041 3 9236 4 7780 72 19848 100092 66812 28617 39645 66797 22 12 957 2542 7 68308 382 96 217 50 44 227 12909 1519 54616 1682 27 124101 45 12279 173381 10 33 21516 147537 59 40 5332 183402 67257 4281 7 172420 498 154897 113480 208 174 1 497 172594 1098 788 13628 39540 3716 748...
result:
ok 199999 numbers
Test #18:
score: 0
Accepted
time: 405ms
memory: 60332kb
input:
199996 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1533 3063 6 30 23551 15871 15871 24063 30 16127 1022 12159 10 1021 254 14 190 12159 510 1533 190 8127 3055 1022 94 24063 766 766 94 254 38 62 8063 10 6 22 1533 24063 1531 1022 30 4079 6079 766 16127 190 2043 8127 510 62 126 8063 126 126 48444 15871 4079 16 6111 22 6 10 78 30 254 94 15871 4 254 1021 ...
result:
ok 200000 numbers
Test #19:
score: 0
Accepted
time: 715ms
memory: 74032kb
input:
199995 11041 115179 115179 153668 153668 847 847 108504 108504 29146 29146 69344 69344 97959 97959 9751 9751 161877 161877 181430 181430 34952 34952 189883 189883 115070 115070 183758 183758 82663 82663 166540 166540 32583 32583 98368 98368 134401 134401 177593 177593 20320 20320 84802 84802 71314 7...
output:
130387 9664 11547 91275 69020 68292 133814 4062 77306 61282 135928 73117 110236 103657 45122 57716 71794 147915 130944 51863 118043 70186 3280 145614 126093 73581 69331 53113 47390 148553 125773 9218 4978 58747 152237 79990 104530 37955 88353 26213 133365 186683 125906 71589 170278 141966 124506 906...
result:
ok 199990 numbers
Test #20:
score: 0
Accepted
time: 801ms
memory: 98132kb
input:
199993 177390 147612 147612 4211 4211 14815 14815 169902 169902 107796 107796 87432 87432 66581 66581 144789 144789 48284 48284 124832 124832 151850 151850 145877 145877 31550 31550 71569 71569 63733 63733 951 951 6788 6788 199487 199487 114893 114893 11399 11399 170687 170687 122411 122411 46734 46...
output:
107762 141285 24282 123780 66318 114627 45030 82414 56308 6384 104567 96050 91967 43940 151582 70456 69859 121641 60747 102655 183088 79543 155264 136617 108988 104594 43276 168667 110178 40707 29012 62994 22555 14804 27491 65920 22536 58571 192497 122141 47921 104042 112261 96620 126104 111319 9733...
result:
ok 199994 numbers
Test #21:
score: 0
Accepted
time: 496ms
memory: 67948kb
input:
199993 1 2 1 3 2 4 1 5 3 6 1 7 5 8 7 9 9 10 7 11 3 12 6 13 4 14 5 15 8 16 14 17 10 18 10 19 15 20 20 21 19 22 13 23 15 24 17 25 22 26 26 27 20 28 28 29 21 30 21 31 25 32 23 33 25 34 31 35 28 36 30 37 34 38 31 39 34 40 36 41 32 42 37 43 42 44 39 45 42 46 41 47 38 48 43 49 40 50 42 51 50 52 49 53 47 5...
output:
51578 38667 1524 13459 21140 3826 59246 2246 47429 55781 53983 77239 20185 106208 53791 70701 8913 35683 57133 100232 55601 50968 69940 56442 18980 6305 94853 29355 52681 96168 83317 11505 21769 51959 100713 61485 514 47185 100363 84120 36280 64865 55201 65700 7318 24265 82609 20438 5870 73828 86460...
result:
ok 199992 numbers
Test #22:
score: 0
Accepted
time: 382ms
memory: 71712kb
input:
199996 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50...
output:
61674 63693 5444 4412 119192 97999 68341 140082 55497 42858 77523 54267 167822 49345 20816 48970 131851 179687 94880 43274 93973 118005 52804 91728 102191 94963 103067 30400 99910 161391 7340 68917 67420 88327 12228 104409 151035 80497 90523 116958 77993 61410 100229 69813 145161 121525 19553 14452 ...
result:
ok 199992 numbers
Test #23:
score: 0
Accepted
time: 413ms
memory: 85252kb
input:
199991 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:
59 48 415 291 69 119538 321 272 334 54 214 41286 367 13805 97857 104 241 255 283 91 323 161 357 125045 132 339 151823 80847 65651 115686 29503 218 53641 258 23 77332 288 45 73 66967 152 299 23692 98685 75 131750 139781 98 350 357 26 4232 254 178 57217 77332 239 448 11508 264 16540 398 117035 405 14 ...
result:
ok 199993 numbers
Test #24:
score: 0
Accepted
time: 640ms
memory: 62992kb
input:
199995 1 113414 2 2284 3 98845 4 44695 5 160127 6 100466 7 194555 8 16596 9 144228 10 80166 11 163524 12 104617 13 156298 14 190763 15 190200 16 51669 17 159037 18 3883 19 169292 20 129486 21 109285 22 177749 23 42088 24 110131 25 34729 26 20820 27 157541 28 11756 29 138395 30 24135 31 153422 32 191...
output:
109204 39278 62211 134886 9 601 181082 41676 2033 116851 72120 27639 11577 38351 77170 54255 33378 82327 102402 74545 8152 64128 31796 148495 415 54543 1354 47764 41935 52287 142939 122745 32683 1725 170345 41430 20010 48221 24637 34819 153209 10982 113155 18968 34947 162078 2043 106717 190000 1108 ...
result:
ok 199999 numbers
Subtask #4:
score: 0
Runtime Error
Test #25:
score: 22
Accepted
time: 771ms
memory: 41596kb
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
78 107329 190250 5672 110415 199160 3826 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 192719 99 191654 80328 481 195140 170809 120515 290 199616 719 142 195166 2607 20737 135444 199768 2433 164666 180527 198261 14511 53672 69060 185790 110874 639 131 2130 188357 150164 2...
result:
ok 199996 numbers
Test #26:
score: -22
Runtime Error
input:
199992 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%