QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#828890 | #9607. 熟练 | Astatinear | 100 ✓ | 1908ms | 206224kb | C++23 | 5.7kb | 2024-12-23 21:35:01 | 2024-12-23 21:35:02 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
using namespace std;
inline char gc()
{
static char buf[100010], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100010, stdin), p1==p2) ? EOF : *p1++;
}
template<typename T> inline void read(T&x)
{
x = 0;
bool f=0;
static char s = gc();
while(s < '0' || s > '9') f |= s=='-', s = gc();
while(s >= '0' && s <= '9') x = (x << 3) + (x << 1) + (s ^ 48), s = gc();
if(f) x = -x;
}
template<typename T> inline void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
}
#define maxn 500005
int c, t;
int n, m;
int fst[maxn], cnt;
struct node
{
int tar, nxt;
}arr[maxn << 1];
void adds(int x, int y)
{
arr[++cnt].tar = y, arr[cnt].nxt = fst[x], fst[x] = cnt;
}
int a[maxn], b[maxn], C[maxn];
int f[maxn][21];
int fa[maxn], son[maxn], dep[maxn], siz[maxn];
int dfn[maxn], rnk[maxn], top[maxn], qwq;
int lg[maxn];
void dfs1(int x, int last)
{
fa[x] = last, siz[x] = 1, dep[x] = dep[last] + 1;
int mxid = 0;
for (int i = fst[x]; i; i = arr[i].nxt)
{
int j = arr[i].tar;
if(j == last) continue;
dfs1(j, x);
siz[x] += siz[j];
if(siz[mxid] < siz[j]) mxid = j;
}
son[x] = mxid;
}
void dfs2(int x, int last)
{
top[x] = last;
dfn[x] = ++qwq, rnk[qwq] = x;
if(son[x]) dfs2(son[x], last);
for (int i = fst[x]; i; i = arr[i].nxt)
{
int j = arr[i].tar;
if((fa[x] == j) || (son[x] == j)) continue;
dfs2(j, j);
}
}
void dfs(int x, int last)
{
f[x][0] = last;
for (int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
for (int i = fst[x]; i; i = arr[i].nxt)
{
int j = arr[i].tar;
if(j == last) continue;
dfs(j, x);
}
}
int lca(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
int p = dep[x], q = dep[y];
for (int i = lg[p - q]; i >= 0; --i) if(p - (1 << i) >= q) p -= (1 << i), x = f[x][i];
if(x == y) return x;
for (int i = lg[p]; i >= 0; --i) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int sum[maxn], maxx;
void get_ans(int x, int last)
{
for (int i = fst[x]; i; i = arr[i].nxt)
{
int j = arr[i].tar;
if(j == last) continue;
get_ans(j, x);
sum[x] += sum[j];
}
maxx = max(maxx, sum[x]);
}
vector<pair<int, int> > query(int x, int y)
{
vector<pair<int, int> > p;
int fx = top[x], fy = top[y];
while(fx != fy)
{
if(dep[fx] > dep[fy])
{
p.push_back(make_pair(dfn[fx], dfn[x]));
x = fa[fx], fx = top[x];
}
else
{
p.push_back(make_pair(dfn[fy], dfn[y]));
y = fa[fy], fy = top[y];
}
}
if(dfn[x] < dfn[y]) p.push_back(make_pair(dfn[x], dfn[y]));
else p.push_back(make_pair(dfn[y], dfn[x]));
return p;
}
struct segmentree
{
int l, r;
pair<int, int> data;
int tag;
}tree[maxn << 2];
void update(int p)
{
tree[p].data = max(tree[p << 1].data, tree[p << 1 | 1].data);
}
void build(int p, int l, int r)
{
tree[p].l = l, tree[p].r = r, tree[p].tag = 0;
if(l == r) return tree[p].data = make_pair(sum[rnk[l]], -l), void(0);
int mid = (l + r) >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
update(p);
}
void pushdown(int p)
{
int tag = tree[p].tag;
if(tag)
{
int l = p << 1, r = p << 1 | 1;
tree[l].tag += tag, tree[r].tag += tag;
tree[l].data.first += tag, tree[r].data.first += tag;
tree[p].tag = 0;
}
}
void change(int p, int l, int r, int x)
{
if(tree[p].l > r || tree[p].r < l) return;
if(tree[p].l >= l && tree[p].r <= r) return tree[p].tag += x, tree[p].data.first += x, void(0);
pushdown(p);
change(p << 1, l, r, x), change(p << 1 | 1, l, r, x);
update(p);
}
pair<int, int> query(int p, int l, int r)
{
if(tree[p].l > r || tree[p].r < l) return make_pair(0, 0);
if(tree[p].l >= l && tree[p].r <= r) return tree[p].data;
pushdown(p);
return max(query(p << 1, l, r), query(p << 1 | 1, l, r));
}
vector<pair<int, int> > route[maxn];
vector<int> path[maxn];
int used[maxn], ans[maxn], color, Key;
void solve(int l, int r)
{
if(l > r) return;
pair<int, int> now = query(1, l, r);
if(now.first < Key) return;
int id = rnk[-now.second];
// cout << "Color : " << color << endl;
// cout << l << " " << r << "qwq" << id << endl;
int num = path[id][used[id]++];
ans[num] = color;
// cout << num << endl;
for (int i = 0; i < route[num].size(); ++i) change(1, route[num][i].first, route[num][i].second, -1);
solve(dfn[id] + siz[id], n);
for (int i = 1; i < route[num].size(); ++i) solve(route[num][i - 1].second + 1, route[num][i].first - 1);
solve(route[num][route[num].size() - 1].second + 1, r);
}
int main()
{
read(c), read(t);
while(t--)
{
qwq = cnt = 0;
maxx = 1;
read(n), read(m);
for (int i = 1; i <= n; ++i) fst[i] = sum[i] = 0, path[i].clear(), used[i] = 0, lg[i] = __lg(i);
lg[0] = 0;
for (int i = 1; i < n; ++i)
{
int x, y;
read(x), read(y);
adds(x, y), adds(y, x);
}
for (int i = 1; i <= m; ++i) read(a[i]), read(b[i]);
dfs(1, 0);
dfs1(1, 0), dfs2(1, 1);
for (int i = 1; i <= m; ++i)
{
if(dfn[a[i]] > dfn[b[i]]) swap(a[i], b[i]);
int c = lca(a[i], b[i]);
sum[c]--, sum[f[c][0]]--, sum[a[i]]++, sum[b[i]]++;
C[i] = c;
path[c].push_back(i);
route[i] = query(a[i], b[i]);
stable_sort(route[i].begin(), route[i].end());
}
get_ans(1, 0);
build(1, 1, n);
for (int i = 1; i <= maxx; ++i) color = i, Key = query(1, 1, n).first, solve(1, n);
printf("%d\n", maxx);
for (int i = 1; i <= m; ++i) printf("%d ", ans[i]);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 83ms
memory: 71544kb
input:
1 100000 1 2 1 1 1 1 3 5 1 2 2 3 2 1 2 3 1 1 1 1 3 3 1 3 1 1 1 1 1 1 4 4 1 2 2 3 3 4 3 3 2 1 3 3 4 2 5 3 1 2 1 3 1 4 2 5 1 1 3 3 3 1 1 5 1 1 1 1 1 1 1 1 1 1 2 5 1 2 2 1 1 2 1 2 1 2 1 2 2 2 1 2 2 2 2 2 4 2 1 2 1 3 1 4 4 4 2 3 2 3 1 2 1 2 1 1 1 1 1 4 1 1 1 1 1 1 1 1 5 3 1 2 2 3 3 4 4 5 3 4 4 5 5 2 2 1...
output:
2 1 2 3 1 3 2 3 2 3 1 2 3 3 1 3 3 2 2 1 1 2 5 1 2 3 4 5 5 1 2 3 4 5 2 1 2 1 1 1 3 1 2 3 4 1 2 3 4 3 2 1 3 1 1 2 1 2 4 1 2 3 4 3 1 2 3 3 3 1 2 3 3 1 1 2 1 2 2 1 2 4 1 2 3 4 3 1 2 3 2 4 1 2 3 4 3 1 1 4 1 2 3 4 1 1 5 1 2 3 4 5 1 1 1 5 1 2 3 4 5 2 1 2 1 3 2 3 2 1 3 1 2 3 ...
result:
ok ok
Subtask #2:
score: 14
Accepted
Dependency #1:
100%
Accepted
Test #2:
score: 14
Accepted
time: 36ms
memory: 120820kb
input:
2 1005 489417 5 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 5...
output:
4 2 1 4 3 4 4 1 3 2 3 4 3 1 1 3 2 3 3 1 3 2 2 3 4 1 2 3 4 3 1 2 3 3 3 4 1 2 3 4 3 2 2 3 1 3 4 1 4 3 2 4 1 2 3 3 4 3 2 3 3 1 4 1 2 3 4 5 2 3 1 4 5 3 1 2 3 3 2 5 1 2 3 4 5 5 2 3 1 4 5 4 2 1 3 4 3 2 1 3 3 4 1 2 3 4 4 3 1 2 4 4 2 1 3 4 3 5 1 3 4 5 2 3 3 3 2 1 2 2 1 1 2 2 5 2 1 3 ...
result:
ok ok
Test #3:
score: 14
Accepted
time: 107ms
memory: 130000kb
input:
2 9250 403459 5 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 5...
output:
5 5 4 2 3 1 4 3 1 2 3 4 4 1 2 3 4 4 1 2 3 4 2 1 1 2 2 4 2 1 3 4 5 1 2 3 4 5 3 1 2 2 3 3 2 2 2 2 1 4 2 3 4 1 2 1 2 2 2 4 3 1 4 4 2 3 3 3 3 1 2 4 2 4 3 1 3 1 3 2 2 2 2 1 1 2 2 2 4 1 2 3 4 3 3 1 2 1 3 4 3 2 1 4 3 3 1 1 2 3 3 2 1 2 3 5 4 5 3 1 2 4 2 1 2 3 4 2 1 1 2 2 4 1 2 2 3 4 ...
result:
ok ok
Test #4:
score: 14
Accepted
time: 55ms
memory: 92424kb
input:
2 120 55394 5 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 ...
output:
3 1 1 3 2 3 2 2 1 2 1 2 4 4 3 1 4 2 4 1 4 2 3 4 4 1 3 4 4 2 3 2 3 1 3 2 5 1 2 3 4 5 4 1 2 3 4 3 2 1 3 3 3 1 2 3 3 2 2 1 2 2 3 1 1 3 2 2 5 2 3 4 5 1 5 1 2 3 4 5 4 1 2 3 4 3 2 3 1 3 3 1 2 2 3 3 2 3 3 1 4 1 2 3 4 4 5 1 2 3 4 5 4 1 2 3 3 4 3 1 3 2 2 3 3 2 3 1 3 5 1 2 3 4 5 4 1 2 ...
result:
ok ok
Test #5:
score: 14
Accepted
time: 75ms
memory: 91872kb
input:
2 6024 82100 5 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 5 13 10 14 8 15 6 16 15 17 3 18 9 19 14 20 19 21 4 22 1 23 22 24 21 25 25 26 11 27 18 28 23 29 7 30 26 31 12 32 2 33 29 34 17 35 34 36 31 37 32 38 13 39 30 40 36 41 33 42 41 43 40 44 16 45 42 46 39 47 20 48 48 49 43 50 46 51 37 52 52 53 4...
output:
5 1 2 3 4 5 4 2 1 4 3 4 4 1 3 4 4 2 4 1 4 2 3 4 4 1 2 3 2 4 3 1 3 2 3 3 1 3 2 3 3 2 1 3 2 5 1 2 3 4 5 3 3 1 3 2 4 3 2 1 4 3 2 1 2 3 3 3 1 1 2 3 1 2 3 1 2 4 3 1 2 3 4 4 2 3 1 2 4 4 3 4 1 2 2 1 2 2 2 5 1 4 5 2 3 3 1 2 2 3 3 5 3 2 4 1 5 4 4 1 3 2 5 1 5 2 4 3 3 1 2 3 2 4 1 3 4 2 ...
result:
ok ok
Test #6:
score: 14
Accepted
time: 43ms
memory: 71696kb
input:
2 483 2200 5 1 2 2 3 1 4 4 5 2 6 2 7 1 8 5 9 7 10 5 11 8 12 3 13 2 14 2 15 1 16 9 17 5 18 6 19 7 20 2 21 3 22 7 23 9 24 11 25 3 26 10 27 11 28 7 29 3 30 3 31 7 32 12 33 1 34 8 35 1 36 8 37 11 38 11 39 3 40 11 41 3 42 10 43 11 44 7 45 9 46 7 47 8 48 7 49 5 50 8 51 9 52 4 53 8 54 11 55 2 56 2 57 8 58 ...
output:
4 1 2 4 3 4 2 1 2 2 2 1 2 2 2 2 1 1 4 3 1 3 2 4 4 1 3 2 3 4 3 3 1 2 3 2 5 1 2 3 4 5 4 4 3 3 1 2 4 4 2 1 3 4 4 1 3 2 4 3 5 1 2 3 4 5 5 4 3 5 1 2 4 2 1 3 3 4 3 3 2 1 3 3 3 1 2 3 3 3 2 2 1 1 2 1 2 2 2 2 1 2 3 3 2 3 3 1 3 1 2 2 3 2 5 1 2 3 4 5 5 2 3 1 4 5 4 1 2 3 3 4 3 2 1 3 1 2 3...
result:
ok ok
Test #7:
score: 14
Accepted
time: 47ms
memory: 73736kb
input:
2 400 2260 5 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 5...
output:
3 3 1 2 1 2 4 1 4 2 3 4 5 1 2 3 4 5 4 2 4 3 1 4 3 3 3 1 2 3 5 1 2 3 4 5 4 2 3 4 2 1 4 1 2 3 4 4 5 1 2 3 4 5 4 3 1 2 3 4 5 2 3 4 1 5 5 1 2 3 4 5 4 1 4 2 3 4 4 1 2 3 4 4 3 1 2 2 3 3 3 2 3 1 1 2 3 1 2 1 3 3 5 2 3 4 5 1 5 1 2 4 5 3 5 1 2 3 4 5 3 2 3 3 1 2 4 1 2 3 4 4 3 1 3 2 3 3 5...
result:
ok ok
Test #8:
score: 14
Accepted
time: 72ms
memory: 94508kb
input:
2 9990 124660 5 1 2 2 3 1 4 4 5 4 6 1 7 6 8 7 9 8 10 1 11 7 12 6 13 8 14 11 15 5 16 12 17 6 18 9 19 17 20 13 21 21 22 20 23 15 24 16 25 10 26 7 27 6 28 1 29 8 30 26 31 17 32 13 33 18 34 13 35 9 36 18 37 28 38 18 39 34 40 10 41 30 42 9 43 17 44 37 45 5 46 26 47 15 48 6 49 28 50 19 51 15 52 45 53 36 5...
output:
4 1 2 3 4 4 4 2 1 3 3 4 5 3 1 4 2 5 5 2 5 3 4 1 4 1 2 3 4 4 1 2 3 4 4 5 1 2 3 4 5 4 1 3 2 3 4 4 1 4 2 3 4 4 1 2 2 3 4 4 4 1 3 2 3 2 2 2 1 2 3 2 1 2 3 3 4 1 2 3 4 2 3 3 2 1 3 3 3 1 2 3 3 2 1 3 3 3 4 2 3 3 4 1 5 2 3 4 1 5 3 2 1 3 3 3 1 1 3 3 2 4 1 3 2 3 4 4 1 2 3 4 4 4 1 2 3 4 ...
result:
ok ok
Test #9:
score: 14
Accepted
time: 84ms
memory: 88052kb
input:
2 9078 76509 5 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...
output:
3 2 1 1 3 3 4 1 4 3 2 4 4 1 3 4 4 2 5 1 2 3 4 5 3 1 2 3 2 5 2 1 3 4 5 4 3 1 2 4 4 2 4 1 3 4 4 4 1 3 4 2 2 1 1 2 2 4 1 3 3 2 4 4 3 1 2 4 5 1 2 3 4 5 4 1 2 3 4 4 1 2 3 4 5 2 3 1 4 5 5 1 2 4 3 5 3 3 2 3 3 1 4 4 1 3 2 4 3 1 2 3 2 3 4 1 2 4 3 5 3 1 2 4 5 3 3 1 2 3 3 3 1 1 2 2 3 4 ...
result:
ok ok
Test #10:
score: 14
Accepted
time: 121ms
memory: 120128kb
input:
2 4147 456368 5 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 6 12 3 13 11 14 5 15 14 16 15 17 13 18 10 19 17 20 2 21 12 22 20 23 9 24 22 25 19 26 25 27 26 28 4 29 8 30 24 31 1 32 16 33 31 34 29 35 34 36 27 37 33 38 38 39 28 40 35 41 18 42 41 43 39 44 7 45 44 46 40 47 37 48 21 49 36 50 46 51 45 52 32 53...
output:
5 1 2 3 4 5 5 2 1 3 4 5 4 1 4 3 2 3 3 1 2 3 1 4 4 4 1 2 3 3 1 2 3 3 4 1 2 3 3 4 4 3 4 1 2 5 4 1 5 2 3 4 3 1 4 2 4 1 2 3 4 5 3 2 4 1 5 3 2 2 1 2 3 5 3 1 4 2 5 3 2 1 2 3 2 1 2 2 1 3 2 1 3 1 3 1 2 1 3 3 4 1 2 3 4 5 1 2 3 4 5 3 2 3 1 2 4 1 3 2 4 3 4 1 2 3 4 5 3 1 2 4 5 3 3 3 1 2 ...
result:
ok ok
Subtask #3:
score: 9
Accepted
Test #11:
score: 9
Accepted
time: 554ms
memory: 202688kb
input:
3 1769 481318 428631 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...
output:
66 61 52 51 14 48 37 23 56 43 62 28 48 58 29 32 34 44 49 22 52 20 63 19 44 15 12 38 33 18 26 17 58 27 31 42 59 46 64 52 30 36 41 24 42 60 17 46 55 60 39 53 37 55 60 31 21 10 62 66 57 47 65 52 50 65 27 57 38 30 45 31 64 51 35 29 14 63 56 42 66 47 20 22 40 49 44 25 61 61 56 36 57 57 54 16 66 38 58 27 ...
result:
ok ok
Test #12:
score: 9
Accepted
time: 366ms
memory: 105440kb
input:
3 5246 78503 54670 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 5...
output:
12758 1529 9377 12419 4227 5079 6413 10150 12748 2506 7658 6489 10585 9678 3649 4669 4115 12706 4486 2477 6146 2652 6911 1781 6028 9370 11626 10170 140 11890 4570 9659 6808 9760 10075 913 10653 12441 8290 7062 5638 3230 11999 6403 2703 313 3762 12283 10447 6445 11301 5704 488 5957 189 4071 5479 1497...
result:
ok ok
Test #13:
score: 9
Accepted
time: 270ms
memory: 71928kb
input:
3 396 1125 1442 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 5...
output:
160 102 86 44 149 137 20 87 122 66 78 63 111 151 94 39 33 73 67 158 80 4 133 139 117 73 85 152 116 31 84 115 155 56 93 92 56 134 126 104 122 83 125 140 69 123 152 92 100 17 140 159 143 129 112 85 104 135 126 40 102 101 9 98 36 153 50 160 90 154 105 45 127 57 124 13 146 136 150 70 109 41 63 38 108 52...
result:
ok ok
Test #14:
score: 9
Accepted
time: 282ms
memory: 74272kb
input:
3 487 1664 2238 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 5...
output:
558 411 55 101 341 354 147 410 355 515 182 65 270 324 265 380 335 234 178 294 379 465 262 15 512 66 358 291 90 273 270 164 555 486 488 263 175 32 171 539 117 430 296 207 465 226 391 204 243 465 209 512 130 250 464 236 165 525 310 357 374 416 488 456 226 468 351 70 91 489 137 450 150 85 552 26 548 53...
result:
ok ok
Test #15:
score: 9
Accepted
time: 1009ms
memory: 206224kb
input:
3 130 498610 459330 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 ...
output:
28970 24650 20800 28907 10178 26152 4436 20938 22230 15181 24291 9646 15472 10979 27085 5317 12232 15546 1089 6881 17731 12599 25200 14515 24823 15631 21561 16946 19907 21863 26583 17682 27599 3578 9255 15391 15005 28031 13189 18052 15648 11693 14452 25365 4434 7550 26971 3107 6069 9751 13569 15990 ...
result:
ok ok
Test #16:
score: 9
Accepted
time: 725ms
memory: 199152kb
input:
3 3566 462541 448340 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...
output:
183 182 152 149 67 90 82 128 117 77 162 80 33 57 100 122 68 83 161 174 162 131 99 143 110 169 59 157 106 109 67 174 132 168 32 181 156 51 135 44 100 127 63 82 142 165 180 96 133 94 168 69 68 53 57 167 170 76 103 160 178 66 93 147 162 89 173 141 107 183 81 169 136 173 79 157 40 129 176 107 163 90 95 ...
result:
ok ok
Subtask #4:
score: 20
Accepted
Test #17:
score: 20
Accepted
time: 8ms
memory: 71656kb
input:
4 37 923 917 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 10 13 4 14 11 15 9 16 8 17 5 18 18 19 2 20 13 21 12 22 14 23 19 24 3 25 16 26 15 27 22 28 28 29 21 30 6 31 31 32 23 33 1 34 17 35 30 36 26 37 37 38 34 39 20 40 40 41 39 42 41 43 38 44 24 45 33 46 42 47 25 48 45 49 29 50 36 51 48 52 43 53 51...
output:
839 839 1 2 834 3 4 5 6 7 8 837 9 10 11 12 13 14 15 16 17 18 834 19 20 839 21 22 23 24 838 25 26 27 28 836 29 839 30 837 31 32 33 34 35 36 37 38 835 39 40 41 42 43 44 45 46 47 832 48 49 50 51 52 53 54 55 839 56 57 837 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 835 839 78 79 80 81 82...
result:
ok ok
Test #18:
score: 20
Accepted
time: 8ms
memory: 71648kb
input:
4 26 910 955 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 5...
output:
417 251 33 180 21 109 349 362 118 324 288 289 226 135 83 359 214 297 275 7 233 34 93 252 47 67 156 276 237 97 406 157 380 215 85 98 92 206 47 216 209 87 301 341 160 402 115 125 385 389 167 354 25 384 169 377 124 266 173 194 6 213 315 11 318 305 194 417 138 386 382 64 347 389 412 20 364 56 238 100 25...
result:
ok ok
Test #19:
score: 20
Accepted
time: 12ms
memory: 74016kb
input:
4 27 932 945 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 2...
output:
161 147 148 149 28 9 150 28 14 36 144 29 29 141 146 30 6 151 30 161 31 32 158 33 10 31 34 36 37 1 35 38 36 37 11 139 151 38 39 144 15 2 40 7 16 39 153 148 119 37 32 33 152 11 41 138 17 34 140 143 42 40 38 39 40 41 41 149 147 15 12 42 35 156 161 43 43 42 160 44 45 36 46 143 8 7 44 24 47 155 43 144 45...
result:
ok ok
Test #20:
score: 20
Accepted
time: 8ms
memory: 71824kb
input:
4 27 915 930 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 5...
output:
473 203 439 256 240 177 141 214 60 257 176 185 450 4 162 421 180 165 118 55 8 311 255 235 200 92 194 403 133 169 29 138 292 199 366 98 457 315 352 411 431 91 142 258 240 236 219 307 150 329 396 290 193 348 2 465 373 276 446 447 248 471 222 247 276 376 111 157 236 259 217 123 458 348 95 71 48 260 293...
result:
ok ok
Test #21:
score: 20
Accepted
time: 12ms
memory: 73684kb
input:
4 20 966 940 1 2 2 3 1 4 4 5 5 6 2 7 2 8 6 9 2 10 10 11 3 12 4 13 6 14 11 15 2 16 1 17 13 18 15 19 16 20 16 21 20 22 5 23 6 24 18 25 21 26 18 27 18 28 7 29 25 30 29 31 21 32 3 33 4 34 32 35 16 36 14 37 15 38 16 39 17 40 4 41 7 42 22 43 1 44 33 45 31 46 37 47 15 48 5 49 30 50 43 51 16 52 47 53 13 54 ...
output:
196 1 56 2 3 57 4 58 59 60 61 5 51 62 6 7 52 182 63 64 8 9 65 193 66 10 67 68 170 69 11 12 70 189 71 72 73 74 75 187 76 77 171 78 191 13 79 14 80 15 81 82 83 16 195 84 172 85 86 17 18 87 184 88 19 53 89 90 91 92 194 20 21 54 93 94 55 95 96 97 98 99 100 101 102 103 22 23 24 25 104 105 26 106 107 27 8...
result:
ok ok
Test #22:
score: 20
Accepted
time: 8ms
memory: 73644kb
input:
4 28 920 959 1 2 2 3 1 4 3 5 2 6 4 7 6 8 3 9 4 10 6 11 11 12 8 13 3 14 4 15 8 16 13 17 3 18 17 19 11 20 14 21 7 22 19 23 7 24 12 25 3 26 12 27 22 28 9 29 15 30 17 31 14 32 8 33 2 34 7 35 12 36 13 37 22 38 25 39 20 40 37 41 11 42 29 43 17 44 23 45 36 46 7 47 27 48 24 49 30 50 28 51 17 52 26 53 46 54 ...
output:
216 93 1 94 59 2 95 149 122 66 67 127 96 68 97 98 99 69 100 101 102 103 104 105 106 3 70 212 71 171 107 4 180 5 72 73 108 215 131 183 109 110 29 30 74 60 31 111 209 75 76 112 160 113 184 216 114 185 6 115 61 116 117 118 119 186 120 77 121 62 63 78 122 123 124 125 126 127 128 129 130 131 132 79 133 8...
result:
ok ok
Test #23:
score: 20
Accepted
time: 15ms
memory: 71952kb
input:
4 24 935 984 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 5...
output:
175 83 166 144 133 164 150 162 132 126 173 132 94 115 8 58 69 172 62 46 121 97 174 148 109 53 131 134 85 159 62 104 173 51 175 110 154 49 58 5 71 48 28 123 107 29 20 90 168 100 75 68 56 93 146 159 166 22 72 88 118 70 174 26 124 117 111 106 98 23 44 36 66 166 61 17 158 63 96 137 126 172 160 47 94 173...
result:
ok ok
Test #24:
score: 20
Accepted
time: 12ms
memory: 69716kb
input:
4 31 919 917 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 2...
output:
588 1 25 26 27 2 28 123 124 125 588 126 127 128 3 129 544 130 533 29 131 132 30 133 134 135 136 31 137 138 545 4 139 5 6 140 141 7 32 142 143 536 538 553 144 145 146 147 8 526 148 149 150 151 152 153 154 9 155 10 588 527 11 156 12 13 157 33 539 158 14 159 160 161 15 162 163 164 165 166 167 168 169 1...
result:
ok ok
Test #25:
score: 20
Accepted
time: 12ms
memory: 71656kb
input:
4 22 986 926 1 2 2 3 1 4 2 5 4 6 6 7 3 8 5 9 7 10 4 11 3 12 4 13 7 14 5 15 3 16 8 17 1 18 8 19 3 20 1 21 5 22 2 23 4 24 8 25 4 26 3 27 2 28 1 29 4 30 2 31 2 32 5 33 3 34 6 35 5 36 5 37 6 38 1 39 8 40 5 41 6 42 3 43 8 44 1 45 8 46 6 47 8 48 4 49 6 50 3 51 8 52 7 53 4 54 5 55 6 56 5 57 4 58 8 59 2 60 ...
output:
123 10 8 1 11 9 10 12 12 7 8 11 11 12 13 13 2 13 14 3 14 4 5 12 9 14 10 15 6 15 10 15 11 13 14 11 16 16 16 7 12 8 17 11 9 17 18 18 15 12 17 19 18 16 10 11 17 12 12 19 13 18 13 13 19 14 14 14 15 13 20 20 14 21 15 20 21 16 19 15 17 22 16 17 21 22 16 23 23 24 22 23 24 17 24 18 25 25 18 19 19 25 18 20 2...
result:
ok ok
Test #26:
score: 20
Accepted
time: 8ms
memory: 73972kb
input:
4 22 931 950 1 2 1 3 2 4 3 5 3 6 2 7 6 8 3 9 7 10 7 11 8 12 5 13 3 14 4 15 2 16 3 17 8 18 1 19 3 20 5 21 5 22 6 23 8 24 3 25 1 26 8 27 8 28 8 29 5 30 6 31 4 32 6 33 3 34 8 35 6 36 6 37 7 38 2 39 3 40 8 41 8 42 3 43 8 44 5 45 6 46 7 47 2 48 2 49 1 50 4 51 7 52 7 53 6 54 3 55 3 56 5 57 1 58 5 59 7 60 ...
output:
648 70 238 71 72 73 74 1 634 606 75 76 77 246 78 2 79 80 247 81 3 82 83 84 85 570 4 608 86 87 88 249 89 90 572 598 91 92 252 93 94 95 96 97 98 99 100 101 102 103 104 609 105 255 602 106 107 256 108 5 109 573 257 110 111 112 610 113 114 6 115 612 7 116 260 610 265 117 118 613 119 120 121 8 122 272 9 ...
result:
ok ok
Test #27:
score: 20
Accepted
time: 11ms
memory: 73944kb
input:
4 24 990 970 1 2 2 3 3 4 4 5 4 6 3 7 5 8 6 9 2 10 2 11 5 12 3 13 4 14 6 15 9 16 7 17 3 18 17 19 10 20 7 21 12 22 2 23 13 24 23 25 20 26 26 27 20 28 11 29 16 30 16 31 16 32 1 33 31 34 26 35 24 36 24 37 13 38 12 39 15 40 29 41 33 42 21 43 6 44 44 45 10 46 29 47 24 48 24 49 30 50 6 51 12 52 21 53 26 54...
output:
675 451 656 1 2 252 253 3 4 5 6 254 438 452 7 674 8 656 9 10 255 256 439 257 258 454 657 456 589 259 260 261 11 262 12 263 264 265 13 14 266 457 15 16 267 268 17 667 269 270 18 271 272 273 19 20 465 671 21 22 274 23 466 275 276 277 278 279 467 590 443 280 24 591 592 281 25 282 283 593 284 654 445 26...
result:
ok ok
Test #28:
score: 20
Accepted
time: 8ms
memory: 71908kb
input:
4 22 971 961 1 2 2 3 1 4 3 5 4 6 6 7 2 8 3 9 2 10 10 11 8 12 11 13 11 14 9 15 9 16 8 17 8 18 10 19 10 20 20 21 13 22 10 23 12 24 12 25 23 26 4 27 18 28 23 29 4 30 5 31 19 32 7 33 20 34 7 35 4 36 36 37 28 38 14 39 15 40 14 41 34 42 19 43 33 44 3 45 33 46 35 47 31 48 9 49 42 50 8 51 36 52 27 53 44 54 ...
output:
377 1 2 136 302 322 137 138 3 139 270 305 4 140 271 342 5 272 141 142 143 144 325 145 146 147 332 148 6 149 7 371 150 119 151 152 153 154 372 275 155 8 156 157 158 159 160 161 311 162 373 9 10 278 11 280 163 164 165 12 13 120 166 14 15 121 167 377 168 16 17 377 18 169 19 20 21 283 170 171 172 22 173...
result:
ok ok
Test #29:
score: 20
Accepted
time: 11ms
memory: 69656kb
input:
4 25 994 999 1 2 1 3 1 4 1 5 1 6 1 7 1 8 8 9 3 10 7 11 9 12 1 13 12 14 11 15 15 16 5 17 16 18 13 19 6 20 4 21 17 22 19 23 2 24 10 25 23 26 20 27 24 28 27 29 18 30 22 31 31 32 32 33 14 34 34 35 26 36 36 37 29 38 21 39 30 40 39 41 28 42 35 43 41 44 25 45 33 46 44 47 42 48 38 49 40 50 50 51 46 52 45 53...
output:
261 255 1 2 3 4 5 6 7 8 9 224 10 11 12 13 14 15 16 17 18 19 20 21 260 22 23 231 24 239 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 256 257 55 56 57 58 59 251 60 61 62 63 64 65 66 67 258 68 69 70 71 259 259 72 73 74 75 76 77 78 79 80 246 81 82 83 84 85 86...
result:
ok ok
Test #30:
score: 20
Accepted
time: 4ms
memory: 73704kb
input:
4 31 943 994 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 5...
output:
34 23 34 17 24 32 29 24 34 19 23 9 19 9 34 12 13 17 11 12 30 28 27 7 26 20 12 21 15 25 33 32 25 22 27 30 14 25 27 10 21 24 17 28 18 7 3 24 19 21 9 28 12 10 20 13 26 28 20 34 10 10 7 27 16 33 4 6 25 22 21 4 15 33 19 25 14 27 25 29 12 26 31 22 3 20 15 10 34 17 28 19 27 30 33 32 27 23 22 30 14 34 23 31...
result:
ok ok
Test #31:
score: 20
Accepted
time: 8ms
memory: 73752kb
input:
4 27 981 972 1 2 1 3 2 4 3 5 5 6 6 7 7 8 1 9 9 10 4 11 11 12 8 13 13 14 14 15 15 16 12 17 16 18 17 19 10 20 20 21 19 22 18 23 21 24 22 25 25 26 23 27 24 28 27 29 29 30 30 31 31 32 28 33 32 34 33 35 35 36 26 37 34 38 38 39 39 40 36 41 41 42 40 43 42 44 37 45 43 46 46 47 44 48 45 49 49 50 50 51 47 52 ...
output:
19 6 7 8 9 10 11 12 13 2 16 16 19 18 8 16 13 16 11 14 13 11 13 18 15 11 15 17 16 17 15 15 13 12 16 14 14 11 17 15 14 6 14 17 15 19 11 18 10 14 19 15 17 18 17 14 10 16 14 18 11 19 11 11 9 15 13 11 18 14 19 18 13 17 14 4 14 6 16 15 12 15 11 16 19 15 18 2 12 16 14 16 13 14 15 11 12 18 14 12 19 4 14 19 ...
result:
ok ok
Test #32:
score: 20
Accepted
time: 8ms
memory: 71568kb
input:
4 27 941 912 1 2 1 3 2 4 3 5 1 6 5 7 1 8 8 9 6 10 1 11 2 12 10 13 3 14 12 15 7 16 1 17 13 18 12 19 6 20 13 21 14 22 16 23 1 24 11 25 16 26 9 27 4 28 1 29 2 30 2 31 4 32 14 33 7 34 7 35 5 36 7 37 7 38 15 39 1 40 5 41 5 42 11 43 7 44 15 45 17 46 3 47 11 48 5 49 13 50 4 51 14 52 6 53 6 54 8 55 2 56 1 5...
output:
150 115 1 133 2 34 3 144 4 35 36 49 46 5 50 47 6 61 7 117 37 3 51 38 48 4 39 8 40 9 51 10 41 90 52 11 5 49 62 12 38 96 6 42 121 13 50 150 91 91 150 43 63 126 52 7 8 53 54 134 9 51 52 95 53 55 56 145 14 54 44 10 55 39 124 11 12 97 64 45 105 13 46 15 16 14 92 47 56 15 65 57 58 146 16 17 97 108 18 57 4...
result:
ok ok
Subtask #5:
score: 22
Accepted
Dependency #4:
100%
Accepted
Test #33:
score: 22
Accepted
time: 263ms
memory: 88748kb
input:
5 496 94286 94269 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 9 12 4 13 3 14 13 15 1 16 5 17 16 18 15 19 18 20 2 21 10 22 12 23 23 24 14 25 19 26 20 27 26 28 8 29 29 30 27 31 21 32 25 33 28 34 22 35 30 36 17 37 32 38 33 39 7 40 38 41 37 42 39 43 11 44 44 45 35 46 40 47 41 48 43 49 24 50 34 51 45 52 47...
output:
27238 1 2 3 4 27193 27186 5 27122 6 7 8 9 10 11 12 13 14 15 16 27073 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 27190 40 41 27144 42 43 44 45 46 27141 47 48 27168 49 50 51 52 53 54 55 56 57 58 59 60 61 62 27196 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 ...
result:
ok ok
Test #34:
score: 22
Accepted
time: 436ms
memory: 93792kb
input:
5 102 87302 98915 1 2 2 3 3 4 4 5 1 6 2 7 3 8 1 9 7 10 3 11 9 12 5 13 2 14 13 15 3 16 9 17 7 18 13 19 19 20 16 21 4 22 20 23 14 24 18 25 17 26 26 27 7 28 4 29 3 30 28 31 16 32 32 33 5 34 13 35 17 36 10 37 19 38 14 39 22 40 22 41 36 42 25 43 43 44 12 45 6 46 33 47 24 48 38 49 8 50 31 51 26 52 47 53 2...
output:
43611 24768 16777 16778 16779 1 2 16780 3 16781 43313 4 5 16782 6 20369 32133 7 8 9 16783 10 24769 16784 24770 11 24771 16785 12 43327 13 14 16786 24772 16787 15 24774 16 24775 16788 17 16789 20370 18 19 24777 24778 16790 16791 20 20371 16792 21 22 23 16793 24780 43379 16794 24 16795 16796 16797 167...
result:
ok ok
Test #35:
score: 22
Accepted
time: 580ms
memory: 100028kb
input:
5 465 95072 88256 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...
output:
58693 18838 13633 18839 18840 13634 1 13635 50566 18841 18842 2 18843 18844 18845 3 4 18846 18847 18848 53838 18849 55632 47693 53839 5 18850 18851 18852 13636 6 18853 18854 18855 18856 18857 50567 50568 18858 58616 47695 7 8 9 18859 18860 18861 58447 18862 10 18863 13637 11 18864 18865 18866 18867 ...
result:
ok ok
Test #36:
score: 22
Accepted
time: 112ms
memory: 79248kb
input:
5 911 9670 12225 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 8 11 6 12 5 13 4 14 7 15 9 16 16 17 11 18 1 19 14 20 15 21 13 22 3 23 20 24 12 25 24 26 26 27 23 28 18 29 27 30 22 31 2 32 19 33 32 34 25 35 34 36 29 37 10 38 28 39 33 40 30 41 38 42 17 43 41 44 36 45 37 46 45 47 40 48 44 49 48 50 50 51 51 52 49 ...
output:
11000 1 2 3 4 10954 5 6 10994 7 8 9 10 11 12 10975 13 14 10990 15 10984 16 17 18 19 20 21 22 23 24 25 26 10956 27 28 10997 29 30 31 32 10933 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 10997 58 10940 59 60 61 62 10963 63 64 65 66 67 68 69 70 71 10963 72 73 74 75 76 77 ...
result:
ok ok
Test #37:
score: 22
Accepted
time: 124ms
memory: 78140kb
input:
5 1077 7078 10459 1 2 1 3 3 4 2 5 3 6 4 7 7 8 3 9 4 10 7 11 9 12 1 13 2 14 8 15 6 16 5 17 5 18 11 19 6 20 14 21 8 22 11 23 12 24 15 25 10 26 10 27 7 28 2 29 7 30 1 31 14 32 7 33 1 34 13 35 11 36 5 37 11 38 8 39 3 40 14 41 3 42 7 43 14 44 6 45 11 46 8 47 13 48 9 49 6 50 4 51 10 52 2 53 12 54 14 55 10...
output:
3386 954 955 1 956 957 958 959 2 960 961 3 4 5 6 2480 962 963 2300 964 7 965 8 966 967 2670 9 2302 968 10 969 970 971 2879 11 972 12 13 973 974 975 14 2671 976 977 978 979 2305 15 980 981 982 2308 983 984 16 17 985 986 987 18 3003 2672 988 989 990 991 992 993 19 994 995 2673 20 21 996 22 23 997 24 9...
result:
ok ok
Test #38:
score: 22
Accepted
time: 163ms
memory: 76636kb
input:
5 942 12731 14938 1 2 2 3 3 4 3 5 2 6 1 7 2 8 4 9 4 10 7 11 7 12 4 13 8 14 6 15 4 16 2 17 10 18 4 19 9 20 3 21 17 22 14 23 6 24 20 25 2 26 3 27 22 28 7 29 15 30 27 31 5 32 19 33 6 34 31 35 11 36 33 37 21 38 10 39 34 40 6 41 20 42 19 43 22 44 27 45 41 46 27 47 34 48 36 49 49 50 26 51 47 52 25 53 35 5...
output:
1051 15 239 28 122 503 151 240 504 505 241 242 243 123 506 124 244 245 246 247 29 507 30 248 249 152 250 31 251 508 225 125 252 509 253 254 510 255 256 511 32 226 512 257 33 513 126 258 514 127 128 515 259 516 379 16 1042 931 948 720 169 129 704 34 170 357 35 230 749 130 288 289 290 488 991 193 194 ...
result:
ok ok
Test #39:
score: 22
Accepted
time: 127ms
memory: 72260kb
input:
5 147 1196 1056 1 2 2 3 2 4 3 5 3 6 5 7 3 8 2 9 3 10 10 11 2 12 3 13 12 14 4 15 4 16 3 17 6 18 6 19 10 20 3 21 9 22 8 23 2 24 2 25 6 26 1 27 4 28 3 29 1 30 11 31 8 32 5 33 5 34 7 35 3 36 9 37 1 38 9 39 6 40 4 41 7 42 5 43 4 44 12 45 2 46 8 47 5 48 8 49 6 50 9 51 11 52 5 53 6 54 2 55 9 56 8 57 10 58 ...
output:
451 262 1 46 263 426 47 2 3 48 264 4 49 5 50 6 265 51 7 52 420 53 266 54 8 55 267 56 268 57 58 9 59 10 11 12 269 60 61 13 62 63 64 65 66 14 67 68 69 270 15 70 16 271 17 427 71 72 421 18 73 19 378 272 380 273 430 20 74 75 76 77 274 275 276 277 278 78 79 422 80 81 279 280 82 21 22 83 281 23 24 381 451...
result:
ok ok
Test #40:
score: 22
Accepted
time: 120ms
memory: 72496kb
input:
5 123 1403 768 1 2 1 3 3 4 1 5 1 6 6 7 2 8 8 9 1 10 3 11 2 12 5 13 5 14 2 15 8 16 10 17 6 18 7 19 8 20 10 21 10 22 10 23 6 24 4 25 4 26 7 27 3 28 3 29 8 30 9 31 4 32 4 33 10 34 8 35 6 36 2 37 3 38 5 39 9 40 2 41 1 42 3 43 1 44 9 45 7 46 2 47 3 48 2 49 3 50 8 51 9 52 5 53 10 54 3 55 3 56 1 57 5 58 2 ...
output:
118 29 1 2 3 31 4 5 6 7 8 9 58 10 11 12 13 14 15 16 40 32 17 41 18 19 20 21 22 23 24 25 26 59 27 28 29 30 31 32 33 34 35 36 37 60 34 38 44 45 118 48 45 61 62 39 44 40 46 42 41 49 50 38 45 43 44 63 42 46 64 39 47 46 43 40 51 65 44 47 48 49 41 52 42 52 45 62 45 47 48 43 48 118 50 53 63 53 44 51 46 52 ...
result:
ok ok
Test #41:
score: 22
Accepted
time: 123ms
memory: 72212kb
input:
5 227 1768 690 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...
output:
345 23 182 177 177 266 332 214 96 231 235 159 98 194 317 226 31 215 86 261 221 73 74 217 260 291 77 86 205 80 219 320 236 41 55 203 294 116 138 189 211 48 319 70 196 174 191 121 324 116 302 129 96 324 258 102 122 215 296 262 23 289 160 165 53 146 56 212 156 201 235 148 73 303 284 117 237 342 175 152...
result:
ok ok
Test #42:
score: 22
Accepted
time: 125ms
memory: 72472kb
input:
5 139 2287 2214 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 5...
output:
695 172 22 173 174 144 636 145 1 1 146 175 147 675 23 176 693 435 177 148 178 2 149 150 151 436 608 2 152 666 608 153 3 179 24 627 25 626 3 26 628 180 613 4 181 27 154 182 155 4 183 437 156 157 5 28 6 7 29 30 184 158 159 656 5 8 653 185 160 695 161 690 9 10 679 616 162 691 163 6 186 684 629 695 164 ...
result:
ok ok
Test #43:
score: 22
Accepted
time: 242ms
memory: 92348kb
input:
5 85 99108 97396 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 ...
output:
48829 33837 1200 20483 31711 46380 13852 13947 35833 38003 23326 16413 8505 15490 11897 38137 9937 32636 4796 16856 39334 22061 26110 22311 16762 42991 15368 39928 43585 29588 993 29356 41799 39871 22393 48699 48417 39282 30808 31837 28811 5961 8815 35858 22865 20072 1417 3803 2656 6458 22504 34726 ...
result:
ok ok
Test #44:
score: 22
Accepted
time: 161ms
memory: 91096kb
input:
5 221 97581 86531 1 2 1 3 1 4 4 5 5 6 1 7 4 8 4 9 7 10 2 11 2 12 2 13 9 14 10 15 13 16 4 17 12 18 10 19 16 20 17 21 6 22 18 23 8 24 17 25 22 26 16 27 22 28 8 29 8 30 11 31 21 32 23 33 19 34 9 35 25 36 10 37 1 38 7 39 38 40 38 41 6 42 35 43 36 44 20 45 20 46 16 47 22 48 21 49 43 50 17 51 17 52 39 53 ...
output:
126 115 105 1 2 3 4 5 106 6 7 8 9 105 10 11 12 109 13 14 15 111 126 16 17 18 97 122 19 20 21 22 23 107 24 25 26 27 28 100 29 30 31 120 32 33 34 35 117 87 36 37 108 38 112 39 40 112 41 42 43 44 45 46 115 47 48 49 50 51 116 52 53 101 90 111 54 55 56 57 58 117 59 60 61 62 63 64 65 92 105 66 67 68 69 70...
result:
ok ok
Test #45:
score: 22
Accepted
time: 180ms
memory: 91324kb
input:
5 125 98543 89905 1 2 2 3 1 4 4 5 4 6 1 7 6 8 1 9 3 10 4 11 7 12 9 13 1 14 4 15 7 16 8 17 5 18 8 19 3 20 6 21 5 22 7 23 6 24 4 25 9 26 8 27 8 28 2 29 9 30 3 31 2 32 1 33 1 34 3 35 9 36 2 37 5 38 8 39 5 40 3 41 6 42 1 43 1 44 8 45 3 46 7 47 5 48 3 49 5 50 9 51 8 52 7 53 7 54 8 55 4 56 9 57 6 58 5 59 ...
output:
10182 248 286 287 249 288 289 290 291 292 250 182 251 252 172 205 192 220 206 193 207 173 229 194 230 1 174 195 231 293 253 254 232 2 3 233 196 175 176 294 177 4 183 208 295 296 297 234 255 235 178 184 256 5 185 209 6 210 298 236 257 179 211 237 186 238 187 188 180 239 181 197 258 182 198 221 299 18...
result:
ok ok
Test #46:
score: 22
Accepted
time: 126ms
memory: 93376kb
input:
5 1256 83133 86248 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 5...
output:
31782 27310 30106 14594 3200 15139 6867 3597 20743 29535 14693 21055 12433 4904 19082 9521 16389 30044 28505 22803 7296 11729 7761 14426 12837 15446 6894 9662 13285 2083 13813 9873 19965 13847 18102 4263 19232 16783 10131 11820 26495 26676 28149 27055 19971 19743 7199 17939 29630 23879 30452 22494 1...
result:
ok ok
Test #47:
score: 22
Accepted
time: 126ms
memory: 78988kb
input:
5 337 8058 14070 1 2 1 3 2 4 2 5 1 6 1 7 6 8 3 9 1 10 8 11 4 12 11 13 8 14 1 15 10 16 4 17 11 18 7 19 8 20 4 21 1 22 8 23 3 24 11 25 12 26 3 27 9 28 6 29 4 30 3 31 11 32 7 33 4 34 9 35 10 36 4 37 4 38 5 39 8 40 3 41 9 42 9 43 4 44 10 45 4 46 5 47 4 48 4 49 6 50 10 51 7 52 11 53 5 54 12 55 12 56 5 57...
output:
4114 1 2 3 4 5 6 7 1054 8 9 10 11 12 1055 13 14 15 1056 16 17 18 1718 19 20 21 22 23 24 25 2692 968 26 1719 27 28 29 30 969 31 32 33 34 3796 35 3619 1720 36 37 970 2695 38 39 3799 40 41 1057 1058 42 43 44 45 46 3623 47 48 49 50 51 52 53 54 55 56 971 57 2700 58 59 60 61 62 1721 1059 63 64 65 1060 106...
result:
ok ok
Test #48:
score: 22
Accepted
time: 189ms
memory: 79756kb
input:
5 443 9541 12325 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 ...
output:
2862 400 671 2300 1838 2627 2468 2443 465 1610 1788 2845 2520 2604 1389 921 1939 2471 569 2058 1704 2424 2037 2292 2790 2480 156 547 1867 2116 1480 771 2640 2238 2857 1949 646 2847 29 1684 2317 2807 1210 1419 1836 1824 2314 556 1346 2728 755 308 668 2527 2850 1454 2198 1931 2800 2397 1204 1279 798 1...
result:
ok ok
Subtask #6:
score: 32
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #49:
score: 32
Accepted
time: 519ms
memory: 203964kb
input:
6 178 497927 412086 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 ...
output:
120 85 114 98 107 53 97 120 39 64 62 63 101 94 15 96 44 65 113 42 120 110 33 107 88 72 74 90 30 40 103 6 116 75 52 38 26 84 50 105 29 118 74 89 111 47 96 105 32 120 60 48 96 69 68 78 93 16 119 114 119 92 14 118 99 40 108 105 118 112 49 24 110 72 63 85 57 114 80 28 58 115 48 68 62 73 106 102 115 62 5...
result:
ok ok
Test #50:
score: 32
Accepted
time: 1102ms
memory: 198912kb
input:
6 3234 454553 464302 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...
output:
232572 201216 230338 121308 60237 186597 175413 99405 2747 85806 130678 195316 119552 16090 208806 200450 108955 173046 85252 179171 84186 127214 224155 102024 174096 228916 182264 175117 99170 173108 57414 84551 130147 155697 104279 161337 94078 46511 142060 146718 219245 225467 55994 175232 11012 ...
result:
ok ok
Test #51:
score: 32
Accepted
time: 1908ms
memory: 160356kb
input:
6 5593 417535 438611 1 2 1 3 1 4 1 5 1 6 1 7 4 8 2 9 1 10 8 11 9 12 12 13 10 14 11 15 14 16 15 17 7 18 6 19 19 20 3 21 20 22 22 23 23 24 16 25 24 26 26 27 25 28 18 29 13 30 27 31 21 32 5 33 30 34 31 35 32 36 34 37 17 38 33 39 38 40 40 41 28 42 36 43 42 44 29 45 37 46 43 47 44 48 35 49 47 50 39 51 50...
output:
347915 1 2 3 4 5 6 7 343433 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 347658 27 28 29 30 31 32 33 345310 34 346587 35 36 37 38 39 40 41 42 346999 43 44 45 347289 46 346896 47 48 49 50 51 347002 52 53 54 55 56 57 58 59 60 61 62 344214 63 64 342899 344732 65 66 67 68 69 70 71 72 73 74 75 ...
result:
ok ok
Test #52:
score: 32
Accepted
time: 1592ms
memory: 109800kb
input:
6 13826 84978 124376 1 2 2 3 3 4 4 5 3 6 1 7 4 8 8 9 7 10 7 11 3 12 5 13 12 14 10 15 6 16 14 17 9 18 15 19 8 20 13 21 12 22 20 23 16 24 23 25 4 26 5 27 2 28 5 29 5 30 17 31 5 32 24 33 11 34 14 35 11 36 25 37 22 38 16 39 11 40 29 41 38 42 17 43 38 44 41 45 17 46 44 47 33 48 42 49 6 50 29 51 51 52 3 5...
output:
80099 65650 1 51206 51207 2 3 4 51208 5 76280 51209 6 7 8 51210 79304 9 76281 10 65651 51211 51212 51213 11 51214 12 65653 51215 13 14 65655 15 16 17 18 79416 19 20 51216 49767 51217 21 65657 51218 22 23 24 75073 51219 25 60844 49100 26 27 28 29 30 31 79393 32 51220 33 51221 65667 51222 51223 34 512...
result:
ok ok
Test #53:
score: 32
Accepted
time: 1250ms
memory: 127448kb
input:
6 3480 135245 82221 1 2 1 3 1 4 1 5 1 6 4 7 3 8 5 9 2 10 6 11 1 12 11 13 13 14 14 15 8 16 10 17 12 18 16 19 7 20 19 21 18 22 20 23 15 24 23 25 24 26 26 27 17 28 22 29 29 30 9 31 31 32 21 33 33 34 25 35 30 36 27 37 37 38 38 39 39 40 36 41 40 42 35 43 34 44 42 45 32 46 43 47 47 48 44 49 45 50 28 51 50...
output:
8376 1 2 3 7913 4742 6553 983 8132 5647 8203 4566 3452 6160 7454 4 6833 2385 2614 6321 3809 7259 4174 577 4570 8231 7939 6990 8363 5 5067 4694 7822 6383 1034 8123 7931 6983 6 5364 2864 7 8 7833 3251 9 4148 8078 548 7794 3702 7663 7458 5306 10 2525 6479 2602 368 2831 93 5498 6837 7913 1399 8022 3251 ...
result:
ok ok
Test #54:
score: 32
Accepted
time: 566ms
memory: 115808kb
input:
6 6213 156426 135199 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...
output:
62086 48411 3629 380 48198 46243 17779 15891 7201 15183 54930 1077 49246 40877 55660 61915 34343 45089 3366 35623 57112 29286 36824 41138 27710 30209 46590 19519 60173 10626 39339 45261 34475 42917 20507 20810 60809 59475 16770 20160 3094 58918 51188 7454 26732 36072 36850 61045 25995 4572 53422 164...
result:
ok ok
Test #55:
score: 32
Accepted
time: 589ms
memory: 72388kb
input:
6 394 1424 1766 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 5...
output:
604 598 599 1 600 46 57 123 546 163 54 124 47 2 125 516 126 164 165 166 3 4 127 128 48 129 58 130 167 131 592 132 133 134 168 135 59 136 604 60 546 61 137 49 169 170 171 138 172 173 541 602 597 603 174 550 599 175 176 139 140 62 5 141 6 177 178 587 549 142 143 144 145 594 146 179 147 50 7 180 148 55...
result:
ok ok
Test #56:
score: 32
Accepted
time: 615ms
memory: 74392kb
input:
6 400 1210 2471 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 5...
output:
1521 429 430 431 1032 432 433 434 1 1272 435 436 1471 1421 437 2 438 439 440 441 1423 1473 3 442 4 443 1276 5 182 1519 1035 1518 444 445 446 1459 183 184 1497 447 448 1041 449 450 185 451 452 186 453 1519 454 1042 6 455 7 456 457 1289 458 1492 1420 459 460 461 1045 1508 1453 462 8 1302 463 1048 1424...
result:
ok ok
Test #57:
score: 32
Accepted
time: 589ms
memory: 74384kb
input:
6 428 1031 1178 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 5...
output:
747 1 161 162 12 163 164 165 2 3 691 13 14 4 15 5 166 167 168 16 655 169 730 17 170 18 6 171 172 173 19 174 7 175 176 20 720 687 21 177 178 179 180 181 666 667 182 8 740 183 716 184 185 9 657 10 11 685 186 22 671 187 688 188 189 23 689 690 190 12 191 192 193 728 24 194 195 658 196 197 198 660 718 19...
result:
ok ok
Test #58:
score: 32
Accepted
time: 612ms
memory: 74396kb
input:
6 433 1412 1032 1 2 1 3 3 4 3 5 5 6 6 7 3 8 3 9 3 10 6 11 3 12 3 13 6 14 4 15 4 16 2 17 6 18 2 19 1 20 1 21 2 22 5 23 4 24 3 25 2 26 4 27 1 28 5 29 1 30 6 31 1 32 4 33 3 34 4 35 3 36 4 37 4 38 3 39 6 40 1 41 1 42 4 43 1 44 2 45 3 46 3 47 5 48 6 49 5 50 4 51 4 52 3 53 3 54 1 55 2 56 2 57 3 58 3 59 2 ...
output:
344 197 1 68 69 70 71 2 72 3 73 4 74 75 76 5 77 201 78 79 80 81 82 6 232 7 83 84 85 86 8 202 87 88 9 10 89 11 90 91 12 13 92 14 15 93 94 95 16 96 17 97 98 99 100 101 102 103 18 19 104 105 20 106 107 108 21 233 22 23 24 25 203 109 110 111 26 27 28 29 112 30 31 209 204 113 114 115 32 33 200 116 117 11...
result:
ok ok
Test #59:
score: 32
Accepted
time: 610ms
memory: 74652kb
input:
6 441 1130 2385 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 7 11 4 12 10 13 1 14 13 15 2 16 12 17 14 18 3 19 19 20 6 21 17 22 11 23 9 24 15 25 16 26 20 27 8 28 21 29 5 30 26 31 27 32 18 33 23 34 22 35 35 36 31 37 33 38 37 39 24 40 40 41 30 42 25 43 41 44 28 45 29 46 44 47 45 48 38 49 47 50 36 51 34 52 48 5...
output:
730 1 2 719 727 3 4 5 6 7 8 328 728 696 9 527 10 11 597 650 12 644 13 697 321 724 582 382 14 15 682 16 545 583 303 329 370 471 349 17 18 584 522 19 20 21 399 531 403 22 639 673 23 640 24 606 632 723 411 318 497 484 346 366 482 599 304 578 25 26 673 330 406 27 28 378 567 305 29 532 723 448 30 563 641...
result:
ok ok
Test #60:
score: 32
Accepted
time: 1081ms
memory: 201300kb
input:
6 2736 454986 470122 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...
output:
204856 111004 45642 121267 146602 18139 43231 179479 199659 189729 99806 121035 35052 135594 119808 32242 98066 190740 169579 136614 99402 192830 124301 73269 44103 23504 140586 115898 197612 169030 118577 60834 136840 140644 86570 56436 174499 58024 118866 23685 110007 99630 189540 25377 111377 111...
result:
ok ok