QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#293784 | #7855. 不跳棋 | JWRuixi | 100 ✓ | 847ms | 194668kb | C++17 | 4.1kb | 2023-12-29 19:04:34 | 2023-12-29 19:04:35 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
// #define ATC
#define IL inline
#define LL long long
#define eb emplace_back
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;
#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif
namespace IO {
char ibuf[1 << 20], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
template<typename _Tp>
inline void write(_Tp x) {
static char stk[64], *top = stk;
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
do *top++ = x % 10, x /= 10;
while (x);
while (top != stk) putchar((*--top) | 48);
}
}
using IO::read;
using IO::write;
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define MP make_pair
constexpr int N = 5e5 + 9, INF = 1e9 + 7;
int n, typ, sz[N], son[N];
vector<int> G[N];
struct vNode {
int v;
LL c;
vNode (int v = INF, LL c = 0) : v(v), c(c) {}
vNode operator + (const vNode &z) const {
return v < z.v ? *this : v > z.v ? z : vNode(v, c + z.c);
}
vNode& operator += (const vNode &z) {
return *this = *this + z;
}
};
/**
* Cluster
* x : upper
* y : lower
* all : dis(x, y)
* v : min length
* u : min length to x
* d : min length to y
*/
struct cNode {
enum {I, C, R} typ = I;
int x, y, all;
vNode v, u, d;
};
cNode C (const cNode &a, const cNode &b) {
cNode c;
c.typ = cNode::C;
c.x = a.x, c.y = b.y;
c.all = a.all + b.all;
c.u = a.u + vNode(a.all + b.u.v, b.u.c);
c.d = b.d + vNode(b.all + a.d.v, a.d.c);
c.v = a.v + b.v + vNode(a.d.v + b.u.v, a.d.c * b.u.c);
return c;
}
cNode R (const cNode &a, const cNode &b) {
cNode c;
c.typ = cNode::R;
c.x = a.x, c.y = a.y;
c.all = a.all;
c.u = a.u + b.u;
c.d = a.d + vNode(a.all + b.u.v, b.u.c);
c.v = a.v + b.v + vNode(a.u.v + b.u.v, a.u.c * b.u.c);
return c;
}
#define ls(p) tr[p].lc
#define rs(p) tr[p].rc
int rt, tot;
struct TNode {
int lc, rc, p, sz;
cNode v;
} tr[N << 2];
IL void dfs1 (int u, int fa) {
sz[u] = 1;
tr[u].v = cNode{cNode::I, fa, u, 1, vNode(), vNode(1, 1), vNode(0, 1)};
tr[u].sz = 1;
if (u > 1) {
G[u].erase(find(G[u].begin(), G[u].end(), fa));
}
for (int v : G[u]) {
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
IL int bld (vi::iterator L, vi::iterator R, auto F) {
if (L == R - 1) {
return *L;
}
int all = 0;
for (auto i = L; i != R; ++i) {
all += tr[*i].sz;
}
vi::iterator mid = L + 1;
int sum = 0;
for (auto i = L; i != R; ++i) {
sum += tr[*i].sz;
if (sum <= all / 2) {
mid = i + 1;
}
}
int x = bld(L, mid, F), y = bld(mid, R, F);
++tot;
ls(tot) = x, rs(tot) = y;
tr[x].p = tot, tr[y].p = tot;
tr[tot].sz = tr[x].sz + tr[y].sz;
tr[tot].v = F(tr[x].v, tr[y].v);
return tot;
}
IL int dfs2 (int u) {
vi vc{u};
for (int p = u; son[p]; p = son[p]) {
vi ve{son[p]};
for (int v : G[p]) {
if (v != son[p]) {
ve.eb(dfs2(v));
}
}
vc.eb(bld(ve.begin(), ve.end(), R));
}
return bld(vc.begin(), vc.end(), C);
}
int main() {
n = read(), typ = read();
for (int i = 1, u, v; i < n; i++) {
u = read(), v = read();
G[u].eb(v);
G[v].eb(u);
}
dfs1(1, 0);
tot = n, rt = dfs2(1);
LL as = 0;
for (int i = 1; i < n - 1; i++) {
LL u = read();
if (typ) {
u ^= as;
}
tr[u].v.v = tr[u].v.u = tr[u].v.d = vNode();
for (u = tr[u].p; u; u = tr[u].p) {
tr[u].v = (tr[u].v.typ == cNode::C ? C : R)(tr[ls(u)].v, tr[rs(u)].v);
}
writesp(tr[rt].v.v.v), writeln(as = tr[rt].v.v.c);
}
}
// I love WHQ!
详细
Test #1:
score: 4
Accepted
time: 12ms
memory: 171444kb
input:
100 0 1 2 2 3 2 4 3 5 4 6 4 7 3 8 7 9 4 10 3 11 5 12 5 13 11 14 13 15 10 16 5 17 13 18 18 19 3 20 3 21 6 22 18 23 5 24 17 25 6 26 8 27 21 28 8 29 24 30 29 31 2 32 3 33 1 34 31 35 34 36 15 37 2 38 4 39 3 40 37 41 8 42 2 43 28 44 10 45 44 46 35 47 4 48 38 49 9 50 6 51 38 52 30 53 39 54 43 55 43 56 26 ...
output:
1 97 1 94 1 93 1 92 1 91 1 89 1 88 1 85 1 84 1 83 1 82 1 81 1 79 1 77 1 76 1 75 1 73 1 70 1 69 1 68 1 67 1 67 1 67 1 67 1 66 1 65 1 64 1 63 1 62 1 61 1 61 1 60 1 58 1 57 1 57 1 52 1 51 1 50 1 47 1 44 1 41 1 39 1 38 1 37 1 36 1 35 1 34 1 29 1 27 1 26 1 26 1 26 1 25 1 24 1 23 1 22 1 22 1 21 1 20 1 18 ...
result:
ok 98 lines
Test #2:
score: 4
Accepted
time: 7ms
memory: 171448kb
input:
100 0 1 2 1 3 3 4 2 5 2 6 1 7 5 8 6 9 8 10 8 11 3 12 4 13 12 14 4 15 1 16 4 17 14 18 17 19 8 20 17 21 9 22 12 23 12 24 16 25 19 26 21 27 15 28 5 29 12 30 19 31 15 32 22 33 6 34 29 35 2 36 22 37 16 38 19 39 17 40 11 41 13 42 30 43 17 44 24 45 21 46 17 47 40 48 20 49 3 50 13 51 16 52 30 53 43 54 41 55...
output:
1 94 1 91 1 90 1 89 1 84 1 83 1 80 1 78 1 77 1 76 1 73 1 72 1 68 1 66 1 66 1 65 1 65 1 62 1 60 1 58 1 54 1 53 1 52 1 51 1 50 1 49 1 47 1 46 1 45 1 40 1 39 1 36 1 36 1 36 1 35 1 34 1 32 1 28 1 27 1 27 1 27 1 27 1 27 1 27 1 24 1 23 1 23 1 21 1 21 1 20 1 20 1 20 1 20 1 19 1 19 1 19 1 18 1 16 1 15 1 14 ...
result:
ok 98 lines
Test #3:
score: 4
Accepted
time: 7ms
memory: 171492kb
input:
100 0 1 2 1 3 1 4 4 5 3 6 1 7 1 8 3 9 9 10 4 11 10 12 3 13 10 14 9 15 11 16 6 17 15 18 8 19 13 20 18 21 21 22 2 23 19 24 7 25 5 26 23 27 22 28 5 29 15 30 2 31 15 32 31 33 26 34 27 35 18 36 14 37 15 38 11 39 11 40 38 41 2 42 12 43 8 44 11 45 42 46 33 47 11 48 5 49 15 50 6 51 35 52 9 53 18 54 33 55 13...
output:
1 95 1 94 1 92 1 89 1 87 1 84 1 82 1 79 1 74 1 73 1 71 1 68 1 66 1 64 1 62 1 61 1 59 1 58 1 56 1 55 1 54 1 51 1 50 1 50 1 50 1 49 1 49 1 48 1 46 1 45 1 41 1 39 1 38 1 35 1 33 1 32 1 30 1 28 1 28 1 27 1 27 1 25 1 22 1 20 1 20 1 19 1 19 1 19 1 17 1 13 1 13 1 13 1 12 1 12 1 12 1 11 1 11 1 10 1 10 1 10 ...
result:
ok 98 lines
Test #4:
score: 4
Accepted
time: 8ms
memory: 171436kb
input:
1000 0 1 2 1 3 3 4 2 5 4 6 3 7 4 8 2 9 7 10 6 11 2 12 2 13 5 14 11 15 15 16 6 17 16 18 2 19 19 20 14 21 20 22 12 23 23 24 3 25 18 26 9 27 23 28 18 29 12 30 28 31 5 32 9 33 11 34 5 35 21 36 23 37 6 38 30 39 29 40 16 41 22 42 41 43 28 44 39 45 9 46 15 47 22 48 3 49 46 50 24 51 34 52 43 53 4 54 33 55 4...
output:
1 998 1 997 1 996 1 994 1 992 1 990 1 988 1 980 1 979 1 977 1 976 1 974 1 970 1 969 1 966 1 961 1 956 1 955 1 954 1 951 1 950 1 948 1 947 1 944 1 943 1 942 1 940 1 938 1 935 1 934 1 931 1 929 1 928 1 927 1 923 1 922 1 921 1 920 1 919 1 918 1 916 1 915 1 912 1 909 1 904 1 903 1 902 1 901 1 901 1 898 ...
result:
ok 998 lines
Test #5:
score: 4
Accepted
time: 16ms
memory: 171544kb
input:
1000 0 1 2 2 3 1 4 2 5 5 6 4 7 2 8 3 9 8 10 10 11 10 12 6 13 7 14 1 15 1 16 11 17 6 18 2 19 12 20 1 21 20 22 19 23 23 24 15 25 10 26 18 27 27 28 28 29 12 30 26 31 16 32 32 33 24 34 6 35 21 36 9 37 8 38 36 39 26 40 15 41 18 42 41 43 39 44 7 45 23 46 3 47 47 48 28 49 26 50 39 51 4 52 45 53 52 54 6 55 ...
output:
1 997 1 996 1 995 1 994 1 990 1 987 1 985 1 984 1 981 1 980 1 975 1 973 1 971 1 970 1 969 1 968 1 966 1 965 1 964 1 963 1 962 1 961 1 960 1 959 1 957 1 956 1 954 1 953 1 952 1 951 1 945 1 944 1 943 1 941 1 939 1 937 1 933 1 931 1 930 1 928 1 926 1 925 1 924 1 921 1 920 1 920 1 918 1 917 1 916 1 914 ...
result:
ok 998 lines
Test #6:
score: 4
Accepted
time: 23ms
memory: 171492kb
input:
1000 0 1 2 2 3 3 4 2 5 1 6 1 7 1 8 3 9 2 10 10 11 3 12 9 13 9 14 10 15 10 16 16 17 16 18 15 19 6 20 17 21 8 22 3 23 13 24 2 25 20 26 10 27 15 28 19 29 7 30 16 31 22 32 26 33 24 34 6 35 35 36 29 37 8 38 7 39 12 40 19 41 34 42 34 43 34 44 10 45 31 46 40 47 47 48 36 49 29 50 7 51 47 52 33 53 47 54 29 5...
output:
1 997 1 996 1 992 1 986 1 985 1 984 1 983 1 982 1 981 1 979 1 976 1 973 1 971 1 966 1 963 1 962 1 958 1 956 1 953 1 952 1 949 1 948 1 947 1 946 1 944 1 943 1 942 1 941 1 941 1 940 1 939 1 938 1 935 1 933 1 932 1 931 1 930 1 929 1 928 1 925 1 923 1 921 1 920 1 920 1 919 1 916 1 914 1 911 1 908 1 906 ...
result:
ok 998 lines
Test #7:
score: 4
Accepted
time: 262ms
memory: 180508kb
input:
200000 0 1 2 2 3 2 4 1 5 3 6 4 7 4 8 3 9 5 10 8 11 8 12 7 13 11 14 11 15 14 16 15 17 7 18 7 19 15 20 15 21 12 22 14 23 9 24 8 25 18 26 22 27 8 28 2 29 15 30 3 31 24 32 10 33 18 34 12 35 3 36 32 37 20 38 37 39 21 40 1 41 28 42 3 43 21 44 22 45 26 46 44 47 47 48 44 49 27 50 41 51 49 52 6 53 27 54 6 55...
output:
1 199998 1 199997 1 199995 1 199992 1 199990 1 199989 1 199988 1 199985 1 199983 1 199980 1 199979 1 199976 1 199975 1 199973 1 199972 1 199971 1 199968 1 199967 1 199959 1 199957 1 199955 1 199954 1 199953 1 199952 1 199950 1 199948 1 199947 1 199945 1 199944 1 199943 1 199942 1 199941 1 199940 1 1...
result:
ok 199998 lines
Test #8:
score: 4
Accepted
time: 267ms
memory: 180488kb
input:
200000 0 1 2 1 3 1 4 1 5 5 6 4 7 2 8 2 9 9 10 8 11 6 12 10 13 6 14 6 15 6 16 12 17 9 18 15 19 10 20 3 21 8 22 15 23 8 24 6 25 8 26 11 27 14 28 27 29 8 30 9 31 24 32 15 33 19 34 26 35 2 36 17 37 15 38 8 39 30 40 11 41 26 42 17 43 41 44 32 45 9 46 30 47 31 48 41 49 38 50 2 51 42 52 35 53 30 54 10 55 2...
output:
1 199997 1 199996 1 199992 1 199990 1 199988 1 199986 1 199985 1 199981 1 199980 1 199979 1 199978 1 199977 1 199976 1 199974 1 199973 1 199971 1 199970 1 199966 1 199964 1 199963 1 199962 1 199961 1 199960 1 199958 1 199957 1 199956 1 199954 1 199953 1 199949 1 199947 1 199946 1 199945 1 199943 1 1...
result:
ok 199998 lines
Test #9:
score: 4
Accepted
time: 247ms
memory: 180572kb
input:
200000 0 1 2 2 3 2 4 2 5 4 6 3 7 4 8 5 9 6 10 8 11 3 12 8 13 11 14 2 15 11 16 6 17 1 18 6 19 2 20 17 21 19 22 1 23 11 24 2 25 12 26 7 27 3 28 6 29 9 30 17 31 12 32 27 33 21 34 27 35 16 36 22 37 23 38 7 39 11 40 8 41 1 42 6 43 40 44 41 45 44 46 34 47 14 48 20 49 47 50 33 51 21 52 14 53 41 54 52 55 37...
output:
1 199996 1 199995 1 199992 1 199989 1 199988 1 199987 1 199986 1 199984 1 199980 1 199975 1 199974 1 199973 1 199971 1 199970 1 199969 1 199968 1 199963 1 199961 1 199958 1 199955 1 199953 1 199951 1 199950 1 199948 1 199947 1 199945 1 199942 1 199938 1 199936 1 199931 1 199930 1 199928 1 199927 1 1...
result:
ok 199998 lines
Test #10:
score: 4
Accepted
time: 175ms
memory: 189300kb
input:
200000 0 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:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #11:
score: 4
Accepted
time: 171ms
memory: 181900kb
input:
200000 0 1 2 1 3 3 4 1 5 1 6 2 7 1 8 7 9 4 10 5 11 7 12 2 13 10 14 11 15 9 16 15 17 13 18 9 19 10 20 14 21 12 22 20 23 22 24 21 25 16 26 20 27 24 28 27 29 27 30 21 31 28 32 24 33 26 34 31 35 29 36 33 37 33 38 38 39 35 40 30 41 36 42 40 43 34 44 44 45 43 46 44 47 45 48 39 49 49 50 41 51 50 52 51 53 4...
output:
1 199997 1 199995 1 199992 1 199988 1 199985 1 199983 1 199981 1 199979 1 199978 1 199976 1 199974 1 199972 1 199971 1 199970 1 199967 1 199964 1 199962 1 199961 1 199959 1 199956 1 199954 1 199951 1 199949 1 199946 1 199943 1 199942 1 199940 1 199939 1 199936 1 199935 1 199934 1 199933 1 199929 1 1...
result:
ok 199998 lines
Test #12:
score: 4
Accepted
time: 176ms
memory: 181824kb
input:
200000 0 1 2 1 3 1 4 4 5 3 6 1 7 2 8 7 9 7 10 9 11 2 12 11 13 12 14 14 15 13 16 10 17 12 18 11 19 14 20 17 21 19 22 12 23 17 24 14 25 19 26 25 27 23 28 26 29 29 30 23 31 31 32 27 33 28 34 26 35 34 36 36 37 34 38 32 39 29 40 40 41 41 42 38 43 37 44 34 45 40 46 38 47 47 48 45 49 40 50 40 51 45 52 50 5...
output:
1 199996 1 199995 1 199992 1 199989 1 199986 1 199985 1 199983 1 199982 1 199981 1 199980 1 199979 1 199976 1 199974 1 199971 1 199969 1 199966 1 199961 1 199960 1 199957 1 199954 1 199953 1 199950 1 199949 1 199946 1 199943 1 199942 1 199938 1 199937 1 199936 1 199935 1 199933 1 199931 1 199929 1 1...
result:
ok 199998 lines
Test #13:
score: 4
Accepted
time: 173ms
memory: 189352kb
input:
200000 1 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:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #14:
score: 4
Accepted
time: 177ms
memory: 189252kb
input:
200000 1 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:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #15:
score: 4
Accepted
time: 106ms
memory: 189260kb
input:
200000 1 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:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #16:
score: 4
Accepted
time: 179ms
memory: 189260kb
input:
200000 1 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:
1 199997 1 199995 1 199993 1 199991 1 199989 1 199987 1 199985 1 199983 1 199981 1 199979 1 199977 1 199975 1 199973 1 199971 1 199969 1 199967 1 199965 1 199963 1 199961 1 199959 1 199957 1 199955 1 199953 1 199951 1 199949 1 199947 1 199945 1 199943 1 199941 1 199939 1 199937 1 199935 1 199933 1 1...
result:
ok 199998 lines
Test #17:
score: 4
Accepted
time: 248ms
memory: 180548kb
input:
200000 1 1 2 1 3 2 4 1 5 3 6 1 7 7 8 7 9 4 10 4 11 11 12 12 13 7 14 10 15 1 16 5 17 11 18 11 19 1 20 19 21 18 22 20 23 21 24 21 25 6 26 24 27 2 28 8 29 29 30 6 31 4 32 14 33 2 34 3 35 18 36 23 37 35 38 10 39 28 40 35 41 17 42 1 43 5 44 14 45 23 46 35 47 10 48 10 49 20 50 41 51 14 52 21 53 7 54 5 55 ...
output:
1 199998 1 199997 1 199996 1 199994 1 199991 1 199990 1 199989 1 199988 1 199986 1 199985 1 199984 1 199982 1 199981 1 199978 1 199977 1 199974 1 199973 1 199970 1 199968 1 199963 1 199962 1 199961 1 199958 1 199957 1 199956 1 199955 1 199954 1 199949 1 199948 1 199947 1 199944 1 199942 1 199938 1 1...
result:
ok 199998 lines
Test #18:
score: 4
Accepted
time: 234ms
memory: 180600kb
input:
200000 1 1 2 2 3 2 4 2 5 4 6 3 7 5 8 5 9 9 10 1 11 2 12 1 13 3 14 10 15 4 16 11 17 6 18 8 19 6 20 7 21 15 22 19 23 20 24 12 25 14 26 18 27 22 28 28 29 16 30 30 31 23 32 9 33 7 34 24 35 7 36 9 37 15 38 8 39 18 40 4 41 30 42 22 43 17 44 17 45 9 46 22 47 21 48 44 49 37 50 44 51 23 52 42 53 16 54 43 55 ...
output:
1 199997 1 199992 1 199991 1 199990 1 199989 1 199986 1 199984 1 199982 1 199980 1 199979 1 199976 1 199975 1 199972 1 199971 1 199970 1 199969 1 199966 1 199965 1 199964 1 199962 1 199960 1 199954 1 199953 1 199950 1 199949 1 199948 1 199945 1 199944 1 199943 1 199942 1 199941 1 199940 1 199938 1 1...
result:
ok 199998 lines
Test #19:
score: 4
Accepted
time: 190ms
memory: 181840kb
input:
200000 1 1 2 1 3 2 4 3 5 5 6 5 7 1 8 3 9 8 10 8 11 7 12 11 13 3 14 4 15 7 16 12 17 9 18 10 19 19 20 15 21 16 22 13 23 13 24 14 25 17 26 17 27 19 28 18 29 24 30 21 31 29 32 24 33 30 34 31 35 34 36 27 37 37 38 34 39 33 40 38 41 34 42 42 43 36 44 35 45 43 46 44 47 41 48 43 49 47 50 48 51 42 52 46 53 49...
output:
1 199996 1 199995 1 199993 1 199992 1 199990 1 199987 1 199985 1 199983 1 199982 1 199980 1 199979 1 199978 1 199977 1 199974 1 199973 1 199971 1 199968 1 199964 1 199960 1 199957 1 199955 1 199950 1 199948 1 199947 1 199944 1 199943 1 199941 1 199939 1 199938 1 199935 1 199933 1 199932 1 199931 1 1...
result:
ok 199998 lines
Test #20:
score: 4
Accepted
time: 193ms
memory: 182856kb
input:
200000 1 1 2 1 3 3 4 3 5 2 6 3 7 6 8 8 9 9 10 6 11 10 12 9 13 8 14 10 15 10 16 16 17 15 18 16 19 18 20 17 21 21 22 20 23 22 24 19 25 21 26 22 27 26 28 23 29 24 30 29 31 30 32 31 33 30 34 32 35 35 36 34 37 36 38 38 39 37 40 35 41 36 42 38 43 38 44 41 45 44 46 41 47 47 48 44 49 44 50 49 51 48 52 49 53...
output:
1 199997 1 199996 1 199994 1 199993 1 199992 1 199991 1 199987 1 199985 1 199984 1 199983 1 199981 1 199979 1 199976 1 199973 1 199971 1 199969 1 199968 1 199966 1 199964 1 199960 1 199958 1 199956 1 199955 1 199953 1 199950 1 199947 1 199945 1 199943 1 199942 1 199940 1 199936 1 199934 1 199931 1 1...
result:
ok 199998 lines
Test #21:
score: 4
Accepted
time: 490ms
memory: 194668kb
input:
500000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
2 124999250001 2 124998750003 2 124998250006 2 124997750010 2 124997250015 2 124996750021 2 124996250028 2 124995750036 2 124995250045 2 124994750055 2 124994250066 2 124993750078 2 124993250091 2 124992750105 2 124992250120 2 124991750136 2 124991250153 2 124990750171 2 124990250190 2 124989750210 ...
result:
ok 499998 lines
Test #22:
score: 4
Accepted
time: 811ms
memory: 192584kb
input:
500000 1 1 2 1 3 2 4 2 5 3 6 2 7 1 8 5 9 5 10 2 11 11 12 9 13 9 14 13 15 12 16 11 17 11 18 12 19 12 20 3 21 7 22 8 23 5 24 12 25 8 26 10 27 22 28 21 29 14 30 29 31 27 32 2 33 33 34 11 35 23 36 33 37 17 38 22 39 25 40 22 41 26 42 42 43 26 44 8 45 28 46 24 47 1 48 17 49 19 50 15 51 38 52 13 53 18 54 1...
output:
1 499998 1 499997 1 499995 1 499994 1 499993 1 499992 1 499991 1 499990 1 499988 1 499987 1 499986 1 499985 1 499983 1 499981 1 499977 1 499976 1 499974 1 499973 1 499971 1 499970 1 499969 1 499968 1 499965 1 499957 1 499949 1 499948 1 499947 1 499946 1 499941 1 499939 1 499938 1 499934 1 499933 1 4...
result:
ok 499998 lines
Test #23:
score: 4
Accepted
time: 847ms
memory: 192616kb
input:
500000 1 1 2 1 3 3 4 4 5 2 6 6 7 4 8 8 9 1 10 9 11 1 12 3 13 10 14 8 15 4 16 8 17 8 18 9 19 14 20 14 21 20 22 14 23 19 24 9 25 19 26 20 27 11 28 23 29 7 30 29 31 12 32 11 33 13 34 5 35 12 36 22 37 13 38 4 39 19 40 1 41 26 42 14 43 37 44 25 45 34 46 32 47 32 48 43 49 7 50 22 51 16 52 8 53 41 54 34 55...
output:
1 499998 1 499997 1 499996 1 499994 1 499989 1 499987 1 499986 1 499985 1 499979 1 499975 1 499974 1 499972 1 499971 1 499970 1 499967 1 499966 1 499965 1 499964 1 499963 1 499961 1 499959 1 499958 1 499956 1 499952 1 499946 1 499943 1 499942 1 499940 1 499939 1 499938 1 499934 1 499933 1 499932 1 4...
result:
ok 499998 lines
Test #24:
score: 4
Accepted
time: 786ms
memory: 192536kb
input:
500000 1 1 2 1 3 1 4 2 5 4 6 3 7 5 8 3 9 4 10 4 11 7 12 1 13 10 14 10 15 3 16 1 17 5 18 7 19 8 20 8 21 9 22 22 23 17 24 12 25 6 26 17 27 7 28 7 29 10 30 28 31 5 32 4 33 18 34 25 35 32 36 27 37 11 38 11 39 1 40 34 41 34 42 34 43 3 44 31 45 32 46 25 47 10 48 31 49 4 50 39 51 29 52 50 53 12 54 45 55 38...
output:
1 499998 1 499997 1 499995 1 499994 1 499990 1 499987 1 499986 1 499985 1 499984 1 499983 1 499981 1 499980 1 499979 1 499977 1 499976 1 499975 1 499973 1 499972 1 499967 1 499964 1 499962 1 499961 1 499959 1 499957 1 499955 1 499954 1 499953 1 499952 1 499951 1 499949 1 499948 1 499947 1 499944 1 4...
result:
ok 499998 lines
Test #25:
score: 4
Accepted
time: 776ms
memory: 192540kb
input:
500000 1 1 2 1 3 1 4 3 5 1 6 6 7 3 8 4 9 3 10 8 11 10 12 2 13 11 14 10 15 5 16 13 17 8 18 12 19 3 20 3 21 10 22 17 23 5 24 18 25 21 26 10 27 2 28 27 29 21 30 14 31 9 32 2 33 26 34 28 35 24 36 27 37 19 38 2 39 37 40 39 41 35 42 31 43 20 44 21 45 15 46 7 47 5 48 25 49 13 50 32 51 50 52 4 53 7 54 38 55...
output:
1 499992 1 499988 1 499987 1 499986 1 499985 1 499984 1 499982 1 499978 1 499977 1 499976 1 499974 1 499972 1 499971 1 499970 1 499969 1 499967 1 499966 1 499965 1 499960 1 499958 1 499957 1 499955 1 499947 1 499941 1 499940 1 499933 1 499932 1 499931 1 499928 1 499927 1 499926 1 499925 1 499924 1 4...
result:
ok 499998 lines