QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#15529 | #791. Mousetrap | dsahifodsaf | 100 ✓ | 239ms | 161464kb | C++20 | 3.4kb | 2021-11-09 22:07:28 | 2022-05-03 21:58:00 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define re register
struct edge {
int to;
edge *nx;
} e[2001000], *la[1001000], *cnt = e;
int f[1001000], q[1001000], fa[1001000], ll[1001000], rr[1001000], no[1001000], vl[1001000], d[1001000],
xl[1001000], clnt, cmt;
inline void addE(re int a, re int b) {
*++cnt = (edge) {
b, la[a]
};
la[a] = cnt;
*++cnt = (edge) {
a, la[b]
};
la[b] = cnt;
}
void dfs(re int a, re int ff) {
re int xx = 0, yy = 0;
fa[a] = ff;
for (re edge *i = la[a]; i; i = i->nx)
if (i->to != ff) {
dfs(i->to, a);
if (f[i->to] > xx)
yy = xx, xx = f[i->to];
else if (f[i->to] > yy)
yy = f[i->to];
f[a]++;
d[a]++;
}
f[a] += yy;
}
int qq[4001000], nn[4001000], lazy[4001000], l1, r1, m1, vis[1001000];
inline void pushup(re int i) {
qq[i << 1] > qq[(i << 1) | 1] ? (qq[i] = qq[i << 1], nn[i] = nn[i << 1]) : (qq[i] = qq[(i << 1) | 1],
nn[i] = nn[(i << 1) | 1]);
}
inline void pushdown(re int i) {
lazy[i << 1] += lazy[i];
lazy[(i << 1) | 1] += lazy[i];
qq[i << 1] += lazy[i];
qq[(i << 1) | 1] += lazy[i];
lazy[i] = 0;
}
void build(re int i, re int l, re int r) {
if (l == r) {
qq[i] = vl[l];
nn[i] = l;
return;
}
re int mid = (l + r) >> 1;
build(i << 1, l, mid);
build((i << 1) | 1, mid + 1, r);
pushup(i);
}
void add(re int i, re int l, re int r) {
if (l >= l1 && r <= r1) {
qq[i] += m1;
lazy[i] += m1;
return;
}
re int mid = (l + r) >> 1;
if (lazy[i])
pushdown(i);
if (mid >= l1)
add(i << 1, l, mid);
if (mid < r1)
add((i << 1) | 1, mid + 1, r);
pushup(i);
}
int find(re int a) {
return vis[a] == a ? a : vis[a] = find(vis[a]);
}
char B[1 << 26], *S = B;
int r() {
for (; *S < '-'; S++)
;
register int x = *S++ -'0';
for (; *S >= '0'; x = (x << 3) + (x << 1) + *S++ -'0')
;
return x;
}
int main() {
fread(B, 1, 1 << 26, stdin);
re int n = r(), t = r(), s = r(), x, y, z;
re long long ans = 0;
for (re int i = 1; i < n; i++)
x = r(), y = r(), addE(x, y);
dfs(t, 0);
for (re int i = s; i != t; i = fa[i])
ll[++clnt] = i;
for (re int i = clnt; i; i--)
xl[i] = d[ll[i]] - 1 + xl[i + 1], vis[i] = i;
xl[1]++;
for (re int i = 1; i <= clnt; i++) {
for (re edge *i1 = la[ll[i]]; i1; i1 = i1->nx)
if (i1->to != fa[ll[i]] && i1->to != ll[i - 1]) {
no[++cmt] = i;
vl[cmt] = xl[i] + f[i1->to];
}
rr[i] = cmt;
}
if (cmt == 0)
puts("0"), exit(0);
build(1, 1, cmt);
for (re int i = 1; i <= cmt; i++) {
x = nn[1];
y = no[x];
z = find(y);
if (!z)
printf("%lld", qq[1] + ans), exit(0);
else {
vis[z] = z - 1;
ans++;
l1 = r1 = x;
m1 = -1 << 25;
add(1, 1, cmt);
l1 = 1, r1 = rr[y], m1 = -1;
add(1, 1, cmt);
}
}
printf("%lld", cmt);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 4ms
memory: 7888kb
input:
10 2 10 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 3ms
memory: 7728kb
input:
10 1 10 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 3ms
memory: 7684kb
input:
10 1 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 3ms
memory: 7864kb
input:
9 1 7 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 4ms
memory: 7728kb
input:
10 1 10 1 2 3 2 4 3 5 3 6 4 7 3 8 7 9 2 10 5
output:
3
result:
ok single line: '3'
Test #6:
score: 0
Accepted
time: 4ms
memory: 7852kb
input:
8 1 8 1 2 3 2 4 3 5 4 6 2 7 6 8 3
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 3ms
memory: 7864kb
input:
10 3 2 3 1 1 2 2 4 2 5 2 6 7 5 8 5 9 6 10 6
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 4ms
memory: 7880kb
input:
10 2 3 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 1 10
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
7 1 2 2 1 3 2 4 2 5 3 6 3 7 4
output:
3
result:
ok single line: '3'
Test #10:
score: 0
Accepted
time: 3ms
memory: 7648kb
input:
2 1 2 1 2
output:
0
result:
ok single line: '0'
Subtask #2:
score: 25
Accepted
Test #11:
score: 25
Accepted
time: 37ms
memory: 65884kb
input:
1000000 1 2 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 5...
output:
36
result:
ok single line: '36'
Test #12:
score: 0
Accepted
time: 33ms
memory: 59604kb
input:
900001 1 2 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...
output:
36
result:
ok single line: '36'
Test #13:
score: 0
Accepted
time: 225ms
memory: 67724kb
input:
1000000 1 2 1 2 3 2 4 2 5 4 6 5 7 3 8 5 9 5 10 2 11 5 12 4 13 5 14 9 15 9 16 10 17 2 18 8 19 7 20 11 21 4 22 5 23 13 24 20 25 23 26 8 27 2 28 5 29 26 30 4 31 16 32 11 33 7 34 18 35 21 36 3 37 19 38 20 39 6 40 37 41 29 42 10 43 28 44 32 45 36 46 22 47 6 48 14 49 20 50 13 51 45 52 37 53 11 54 45 55 49...
output:
60
result:
ok single line: '60'
Test #14:
score: 0
Accepted
time: 93ms
memory: 35524kb
input:
500000 1 2 1 2 3 2 4 3 5 4 6 2 7 6 8 7 9 5 10 3 11 6 12 6 13 7 14 11 15 12 16 5 17 12 18 12 19 11 20 16 21 11 22 3 23 18 24 18 25 17 26 3 27 10 28 22 29 16 30 3 31 27 32 23 33 20 34 29 35 31 36 28 37 12 38 17 39 2 40 22 41 15 42 17 43 9 44 9 45 12 46 14 47 26 48 20 49 7 50 8 51 42 52 46 53 49 54 18 ...
output:
74
result:
ok single line: '74'
Test #15:
score: 0
Accepted
time: 239ms
memory: 67660kb
input:
1000000 1 2 1 2 3 2 4 2 5 3 6 2 7 5 8 7 9 2 10 2 11 2 12 5 13 8 14 11 15 2 16 2 17 2 18 11 19 16 20 17 21 14 22 4 23 22 24 21 25 21 26 2 27 14 28 22 29 9 30 14 31 18 32 26 33 25 34 18 35 34 36 16 37 24 38 29 39 35 40 18 41 34 42 12 43 18 44 30 45 14 46 19 47 7 48 37 49 48 50 30 51 41 52 13 53 51 54 ...
output:
69
result:
ok single line: '69'
Test #16:
score: 0
Accepted
time: 205ms
memory: 67680kb
input:
999999 1 2 1 2 3 2 4 3 5 4 6 5 7 6 8 4 9 8 10 5 11 10 12 2 13 12 14 12 15 4 16 3 17 15 18 14 19 6 20 16 21 2 22 17 23 22 24 2 25 19 26 24 27 10 28 6 29 25 30 11 31 2 32 11 33 17 34 14 35 32 36 28 37 7 38 9 39 7 40 18 41 29 42 16 43 38 44 34 45 42 46 22 47 32 48 34 49 21 50 30 51 43 52 26 53 7 54 22 ...
output:
67
result:
ok single line: '67'
Subtask #3:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #17:
score: 20
Accepted
time: 1ms
memory: 7888kb
input:
43 2 5 1 2 1 3 3 4 4 5 5 11 11 12 11 13 4 9 6 9 9 14 9 15 9 16 4 10 10 17 10 18 10 19 10 20 8 21 8 22 8 23 8 24 8 25 8 26 8 27 8 28 8 29 8 30 1 8 7 1 7 31 7 32 7 33 7 34 7 35 7 36 7 37 7 38 7 39 7 40 9 41 10 42 10 43
output:
7
result:
ok single line: '7'
Test #18:
score: 0
Accepted
time: 4ms
memory: 7948kb
input:
1000 1 1000 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 5...
output:
9
result:
ok single line: '9'
Test #19:
score: 0
Accepted
time: 4ms
memory: 7880kb
input:
999 1 20 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:
14
result:
ok single line: '14'
Test #20:
score: 0
Accepted
time: 3ms
memory: 7948kb
input:
1000 1 998 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 ...
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 1ms
memory: 7676kb
input:
901 1 901 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 5...
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 2ms
memory: 7820kb
input:
1000 1 150 1 2 3 2 4 3 5 2 6 5 7 2 8 6 9 2 10 4 11 3 12 10 13 12 14 11 15 3 16 12 17 12 18 14 19 18 20 10 21 4 22 13 23 13 24 13 25 10 26 13 27 17 28 20 29 14 30 29 31 21 32 29 33 27 34 19 35 7 36 24 37 2 38 6 39 17 40 19 41 40 42 23 43 15 44 17 45 25 46 14 47 24 48 13 49 32 50 28 51 3 52 42 53 52 5...
output:
31
result:
ok single line: '31'
Test #23:
score: 0
Accepted
time: 2ms
memory: 7828kb
input:
998 1 833 1 2 3 2 4 3 5 4 6 4 7 2 8 7 9 7 10 5 11 3 12 3 13 10 14 6 15 10 16 13 17 2 18 13 19 8 20 15 21 10 22 11 23 13 24 13 25 5 26 21 27 4 28 12 29 4 30 9 31 28 32 21 33 32 34 24 35 33 36 14 37 29 38 31 39 5 40 6 41 12 42 24 43 27 44 21 45 12 46 18 47 13 48 39 49 40 50 13 51 50 52 3 53 40 54 32 5...
output:
40
result:
ok single line: '40'
Test #24:
score: 0
Accepted
time: 1ms
memory: 7868kb
input:
1000 1 100 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 ...
output:
108
result:
ok single line: '108'
Test #25:
score: 0
Accepted
time: 3ms
memory: 7832kb
input:
999 1 99 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...
output:
107
result:
ok single line: '107'
Test #26:
score: 0
Accepted
time: 1ms
memory: 7912kb
input:
1000 1 100 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 ...
output:
232
result:
ok single line: '232'
Test #27:
score: 0
Accepted
time: 2ms
memory: 7876kb
input:
990 1 99 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...
output:
231
result:
ok single line: '231'
Test #28:
score: 0
Accepted
time: 2ms
memory: 7876kb
input:
666 1 66 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...
output:
158
result:
ok single line: '158'
Subtask #4:
score: 35
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #29:
score: 35
Accepted
time: 2ms
memory: 7932kb
input:
43 2 5 1 2 1 3 3 4 4 5 5 11 11 12 11 13 4 9 6 9 9 14 9 15 9 16 4 10 10 17 10 18 10 19 10 20 8 21 8 22 8 23 8 24 8 25 8 26 8 27 8 28 8 29 8 30 1 8 7 1 7 31 7 32 7 33 7 34 7 35 7 36 7 37 7 38 7 39 7 40 9 41 10 42 10 43
output:
7
result:
ok single line: '7'
Test #30:
score: 0
Accepted
time: 29ms
memory: 65892kb
input:
1000000 1 20 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 ...
output:
34
result:
ok single line: '34'
Test #31:
score: 0
Accepted
time: 42ms
memory: 65948kb
input:
999999 1 999999 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 ...
output:
18
result:
ok single line: '18'
Test #32:
score: 0
Accepted
time: 59ms
memory: 161464kb
input:
1000000 1 1000000 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:
0
result:
ok single line: '0'
Test #33:
score: 0
Accepted
time: 42ms
memory: 146160kb
input:
999999 1 16 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...
output:
1
result:
ok single line: '1'
Test #34:
score: 0
Accepted
time: 213ms
memory: 67708kb
input:
1000000 1 98017 1 2 3 2 4 2 5 4 6 4 7 6 8 6 9 2 10 8 11 2 12 7 13 5 14 8 15 4 16 8 17 2 18 9 19 17 20 16 21 17 22 2 23 16 24 14 25 2 26 6 27 21 28 25 29 15 30 8 31 7 32 12 33 9 34 33 35 12 36 5 37 10 38 17 39 15 40 37 41 25 42 27 43 12 44 25 45 9 46 9 47 19 48 3 49 18 50 28 51 27 52 3 53 3 54 28 55 ...
output:
90
result:
ok single line: '90'
Test #35:
score: 0
Accepted
time: 238ms
memory: 67676kb
input:
999999 1 906874 1 2 3 2 4 2 5 4 6 2 7 3 8 3 9 5 10 9 11 10 12 6 13 2 14 13 15 11 16 2 17 7 18 12 19 16 20 2 21 9 22 20 23 9 24 7 25 22 26 3 27 15 28 9 29 27 30 15 31 15 32 23 33 19 34 15 35 25 36 29 37 25 38 23 39 16 40 22 41 5 42 13 43 36 44 34 45 15 46 12 47 3 48 45 49 2 50 37 51 2 52 4 53 17 54 4...
output:
72
result:
ok single line: '72'
Test #36:
score: 0
Accepted
time: 192ms
memory: 82984kb
input:
1000000 1 100000 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:
230404
result:
ok single line: '230404'
Test #37:
score: 0
Accepted
time: 234ms
memory: 82980kb
input:
999999 1 99999 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:
230321
result:
ok single line: '230321'
Test #38:
score: 0
Accepted
time: 176ms
memory: 76968kb
input:
1000000 1 100000 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:
100006
result:
ok single line: '100006'
Test #39:
score: 0
Accepted
time: 194ms
memory: 77076kb
input:
999999 1 99999 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:
100001
result:
ok single line: '100001'
Test #40:
score: 0
Accepted
time: 184ms
memory: 76940kb
input:
1000000 1 100000 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:
100005
result:
ok single line: '100005'