QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#658747	#9491. 生命的循环	yyyyxh	100 ✓	579ms	34768kb	C++14	5.9kb	2024-10-19 17:31:22	2024-10-19 17:31:24

Judging History

你现在查看的是最新测评结果

[2024-10-19 17:31:24]
评测

测评结果：100
用时：579ms
内存：34768kb

查看

[2024-10-19 17:31:22]
提交

answer

#include <bitset>
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
int read() {
    char c = getchar();
    int x = 0;
    while (c < 48 || c > 57)
        c = getchar();
    do
        x = x * 10 + (c ^ 48), c = getchar();
    while (c >= 48 && c <= 57);
    return x;
}
const int N = 50003, M = 100003, B = 101, I = 2520, P = 1000000009;
typedef long long ll;
int n, m, num, cnt;
int hd[N], ver[M], nxt[M], val[M], tot;
ll dis[N];
int bel[N];
void add(int u, int v, int w) {
    nxt[++tot] = hd[u];
    hd[u] = tot;
    ver[tot] = v;
    val[tot] = w;
}
inline void chmn(int &x, int v) {
    if (x > v)
        x = v;
}
inline int gcd(int a, int b) {
    for (int t; b; t = b, b = a % b, a = t)
        ;
    return a;
}
int qp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = (ll)res * a % P;
        a = (ll)a * a % P;
        b >>= 1;
    }
    return res;
}
int dfn[N], low[N];
int stk[N], tp;
bool ins[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++num;
    ins[stk[++tp] = u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = ver[i];
        if (!dfn[v])
            dis[v] = dis[u] + val[i], tarjan(v), chmn(low[u], low[v]);
        else if (ins[v])
            chmn(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int x;
        ++cnt;
        do {
            x = stk[tp--];
            bel[x] = cnt;
            ins[x] = 0;
        } while (x != u);
    }
}
int g[N], w[N], ex[B];
vector<int> adj[N];
bitset<B> md[N][B], vis[N][B], msk[B], ava[B];
void trav(int u, int g, int t) {
    if (md[u][g][t])
        return;
    md[u][g].set(t);
    for (int i = hd[u]; i; i = nxt[i])
        trav(ver[i], g, (t + val[i]) % g);
}
void dfs(int u, int g, int t) {
    g = gcd(g, w[u]);
    t %= g;
    if (vis[u][g][t])
        return;
    vis[u][g].set(t);
    for (int i = hd[u]; i; i = nxt[i])
        dfs(ver[i], g, t + val[i]);
}
int main() {
    n = read();
    m = read();
    read();
    assert(n <= 5000);
    assert(m <= 10000);
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        assert(w <= B);
    }
    tarjan(1);
    if (!dfn[n]) {
        puts("1");
        return 0;
    }
    for (int u = 1; u <= n; ++u)
        if (dfn[u]) {
            for (int i = hd[u]; i; i = nxt[i]) {
                int v = ver[i];
                if (bel[v] == bel[u])
                    g[bel[u]] = gcd(g[bel[u]], abs(dis[v] - dis[u] - val[i]));
                else
                    adj[bel[u]].emplace_back(bel[v]);
            }
        }
    bool isdag = 1;
    for (int i = 1; i <= n; ++i) {
        w[i] = g[bel[i]];
        if (w[i])
            isdag = 0;
        assert(w[i] <= B);
    }
    if (isdag) {
        puts("1");
        return 0;
    }
    for (int x = 1; x < B; ++x)
        trav(1, x, 0);
    for (int i = 1; i <= n; ++i)
        if (w[i]) {
            for (int t = 0; t < w[i]; ++t)
                if (md[i][w[i]][t])
                    dfs(i, w[i], t);
        }
    for (int t = 1; t < B; ++t)
        for (int i = 0; i < t; ++i)
            vis[n][t].flip(i);
    for (int o = 0; o < I; ++o) {
        for (int t = 1; t < B; ++t) {
            msk[t].reset();
            for (int i = 0; i < t; ++i)
                msk[t].set(i);
        }
        for (int t = 1; t < B; ++t) {
            int _t = t / gcd(I, t);
            bitset<B> cur;
            for (int p = 0; p < _t; ++p)
                if (vis[n][t][(p * I + o) % t])
                    cur.set(p);
            msk[_t] &= cur;
        }
        msk[4] &= (msk[2] << 2) | msk[2];
        msk[8] &= (msk[4] << 4) | msk[4];
        msk[9] &= (msk[3] << 6) | (msk[3] << 3) | msk[3];
        bool fl = 0;
        for (int t = 1; t < B; ++t)
            if (msk[t].none()) {
                fl = 1;
                break;
            }
        if (fl)
            continue;
        for (int t = 1; t < B; ++t) {
            int _t = t / gcd(I, t);
            for (int p = 0; p < _t; ++p) {
                int q = (p * I + o) % t;
                if (vis[n][t][q]) {
                    if (_t == 1) {
                        ava[t].set(q);
                        continue;
                    }
                    if (_t == 2 || _t == 4 || _t == 8) {
                        for (int i = p; i < 8; i += _t)
                            if (msk[8][i]) {
                                ava[t].set(q);
                                break;
                            }
                        continue;
                    }
                    if (_t == 3 || _t == 9) {
                        for (int i = p; i < 9; i += _t)
                            if (msk[9][i]) {
                                ava[t].set(q);
                                break;
                            }
                        continue;
                    }
                    if (msk[_t][p]) {
                        ava[t].set(q);
                        continue;
                    }
                }
            }
        }
    }
    for (int t = 1; t < B; ++t)
        for (int p = 1; p <= t; ++p)
            if (t % p == 0) {
                bool fl = 1;
                for (int i = p; i < t; ++i)
                    if (ava[t][i - p] != ava[t][i]) {
                        fl = 0;
                        break;
                    }
                if (fl) {
                    int cur = p;
                    for (int x = 2; x < B; ++x) {
                        int c = 0;
                        while (cur % x == 0)
                            cur /= x, ++c;
                        ex[x] = max(ex[x], c);
                    }
                    break;
                }
            }
    int res = 1;
    for (int x = 2; x < B; ++x)
        res = (ll)res * qp(x, ex[x]) % P;
    printf("%d\n", res);
    return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 1ms

memory: 5652kb

input:

output:

result:

ok single line: '1'

Test #2:

score: 1

Accepted

time: 1ms

memory: 7848kb

input:

3000 10000 1
2941 1762 34
1456 1466 41
1279 2756 45
396 2841 46
579 12 78
2654 888 18
1656 237 58
1820 2775 80
426 165 3
994 1141 92
1617 1851 28
2449 2082 75
1438 2206 34
2657 774 78
942 1156 40
2329 176 92
858 2172 84
1161 2798 72
982 435 43
1674 1274 88
2827 979 9
1003 1165 50
907 774 81
1142 204...

output:

result:

ok single line: '1'

Subtask #2:

score: 8

Accepted

Test #3:

score: 8

Accepted

time: 35ms

memory: 5880kb

input:

output:

result:

ok single line: '2'

Test #4:

score: 8

Accepted

time: 36ms

memory: 7916kb

input:

output:

result:

ok single line: '60'

Test #5:

score: 8

Accepted

time: 35ms

memory: 7976kb

input:

output:

result:

ok single line: '120'

Subtask #3:

score: 11

Accepted

Test #6:

score: 11

Accepted

time: 217ms

memory: 30584kb

input:

5000 5259 3
1 8 5
8 7 1
7 9 5
9 4 2
4 5 4
5 3 1
3 2 2
2 6 1
6 10 3
10 1 4
5 11 46
11 5 38
2 14 14
14 13 22
13 15 12
15 12 14
12 16 21
16 2 15
7 26 0
26 28 2
28 25 1
25 23 2
23 20 4
20 24 1
24 22 1
22 21 1
21 27 3
27 30 0
30 19 4
19 18 3
18 17 3
17 29 2
29 7 1
14 33 12
33 31 13
31 36 11
36 34 5
34 38...

output:

result:

ok single line: '14'

Test #7:

score: 11

Accepted

time: 89ms

memory: 16048kb

input:

2000 2189 3
1 2 0
2 1 0
2 3 0
3 4 0
4 2 0
2 5 0
5 2 0
3 6 25
6 3 23
2 18 4
18 16 0
16 8 5
8 9 3
9 19 8
19 12 5
12 23 1
23 24 6
24 10 5
10 15 6
15 17 6
17 21 9
21 22 4
22 7 6
7 25 5
25 11 4
11 20 5
20 13 5
13 14 6
14 2 3
17 26 0
26 17 0
26 28 0
28 27 0
27 26 0
3 93 0
93 70 1
70 158 0
158 95 1
95 189 ...

output:

result:

ok single line: '48'

Test #8:

score: 11

Accepted

time: 166ms

memory: 6912kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 10

Accepted

Dependency #3:

100%

Accepted

Test #9:

score: 10

Accepted

time: 173ms

memory: 28576kb

input:

5000 5287 4
1 2 41
1 20 1
20 21 2
21 38 1
38 32 1
32 40 0
40 8 3
8 35 2
35 15 0
15 19 2
19 31 2
31 12 1
12 50 4
50 36 3
36 5 1
5 22 1
22 43 2
43 26 0
26 25 3
25 23 0
23 17 3
17 42 1
42 13 4
13 9 3
9 37 1
37 52 2
52 4 1
4 49 1
49 48 3
48 24 1
24 6 0
6 55 2
55 30 0
30 18 0
18 11 1
11 14 0
14 51 2
51 1...

output:

result:

ok single line: '30'

Test #10:

score: 10

Accepted

time: 281ms

memory: 14144kb

input:

5000 10000 4
4998 4999 12
4999 5000 18
5000 4998 42
1 2 17
2 3 43
3 4 12
4 5 32
5 6 10
6 7 45
7 8 22
8 9 17
9 10 45
10 11 33
11 12 1
12 13 10
13 14 2
14 15 43
15 16 27
16 17 23
17 18 23
18 19 30
19 20 9
20 21 19
21 22 30
22 23 20
23 24 8
24 25 29
25 26 18
26 27 34
27 28 4
28 29 47
29 30 36
30 31 32
...

output:

result:

ok single line: '12'

Subtask #5:

score: 19

Accepted

Test #11:

score: 19

Accepted

time: 332ms

memory: 9152kb

input:

767 10000 5
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 2 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 13 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
...

output:

result:

ok single line: '1'

Test #12:

score: 19

Accepted

time: 45ms

memory: 8028kb

input:

output:

381798563

result:

ok single line: '381798563'

Test #13:

score: 19

Accepted

time: 48ms

memory: 6008kb

input:

output:

672589923

result:

ok single line: '672589923'

Test #14:

score: 19

Accepted

time: 124ms

memory: 6148kb

input:

output:

result:

ok single line: '1'

Test #15:

score: 19

Accepted

time: 41ms

memory: 5972kb

input:

output:

868803081

result:

ok single line: '868803081'

Subtask #6:

score: 9

Accepted

Test #16:

score: 9

Accepted

time: 42ms

memory: 6068kb

input:

output:

result:

ok single line: '7398268'

Test #17:

score: 9

Accepted

time: 30ms

memory: 6012kb

input:

output:

result:

ok single line: '16'

Test #18:

score: 9

Accepted

time: 35ms

memory: 7964kb

input:

output:

714737421

result:

ok single line: '714737421'

Test #19:

score: 9

Accepted

time: 326ms

memory: 11132kb

input:

767 10000 6
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 2 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 13 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
...

output:

result:

ok single line: '1'

Test #20:

score: 9

Accepted

time: 554ms

memory: 34768kb

input:

5000 10000 6
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

result:

ok single line: '9'

Subtask #7:

score: 18

Accepted

Test #21:

score: 18

Accepted

time: 26ms

memory: 8012kb

input:

output:

result:

ok single line: '1'

Test #22:

score: 18

Accepted

time: 26ms

memory: 8132kb

input:

output:

result:

ok single line: '3063060'

Test #23:

score: 18

Accepted

time: 26ms

memory: 7972kb

input:

output:

result:

ok single line: '3423420'

Test #24:

score: 18

Accepted

time: 27ms

memory: 8068kb

input:

output:

346393023

result:

ok single line: '346393023'

Test #25:

score: 18

Accepted

time: 30ms

memory: 5984kb

input:

output:

528923553

result:

ok single line: '528923553'

Test #26:

score: 18

Accepted

time: 26ms

memory: 8044kb

input:

output:

result:

ok single line: '1492260'

Test #27:

score: 18

Accepted

time: 579ms

memory: 22572kb

input:

5000 10000 7
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

result:

ok single line: '3'

Test #28:

score: 18

Accepted

time: 31ms

memory: 8076kb

input:

output:

89541839

result:

ok single line: '89541839'

Test #29:

score: 18

Accepted

time: 34ms

memory: 6084kb

input:

output:

160733989

result:

ok single line: '160733989'

Test #30:

score: 18

Accepted

time: 30ms

memory: 8012kb

input:

output:

767157300

result:

ok single line: '767157300'

Test #31:

score: 18

Accepted

time: 31ms

memory: 5980kb

input:

output:

362040671

result:

ok single line: '362040671'

Test #32:

score: 18

Accepted

time: 29ms

memory: 5852kb

input:

output:

result:

ok single line: '414120'

Test #33:

score: 18

Accepted

time: 90ms

memory: 10700kb

input:

1452 2220 7
1 525 0
525 925 1
925 1043 1
1043 825 0
825 831 0
831 804 1
804 121 1
121 1012 1
1012 1114 1
1114 1398 0
1398 264 1
264 235 0
235 1284 0
1284 1020 0
1020 792 0
792 375 1
375 885 1
885 1411 1
1411 1027 1
1027 857 0
857 180 1
180 1361 1
1361 565 1
565 1430 0
1430 404 1
404 1156 0
1156 646 ...

output:

result:

ok single line: '7020'

Test #34:

score: 18

Accepted

time: 92ms

memory: 10824kb

input:

1452 2239 7
1 1117 1
1117 693 0
693 1182 1
1182 1200 1
1200 105 1
105 138 0
138 893 0
893 1136 0
1136 622 0
622 843 0
843 954 0
954 820 0
820 1139 1
1139 1362 0
1362 509 1
509 525 1
525 1381 1
1381 7 1
7 499 0
499 534 1
534 407 0
407 29 1
29 1436 1
1436 197 0
197 930 0
930 1410 0
1410 337 1
337 971 ...

output:

result:

ok single line: '9828'

Test #35:

score: 18

Accepted

time: 309ms

memory: 24352kb

input:

4932 9860 7
1 872 1
872 900 0
900 1617 1
1617 3242 1
3242 380 0
380 178 1
178 3702 0
3702 4866 1
4866 4846 1
4846 1086 0
1086 41 1
41 1271 1
1271 4767 1
4767 3082 1
3082 3759 1
3759 2723 1
2723 1808 0
1808 2024 1
2024 971 0
971 3935 0
3935 665 0
665 2597 0
2597 3670 0
3670 387 0
387 1573 1
1573 2869...

output:

89541839

result:

ok single line: '89541839'

Subtask #8:

score: 24

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Test #36:

score: 24

Accepted

time: 246ms

memory: 18876kb

input:

3962 9999 8
1 1680 1
1680 3471 0
3471 720 1
720 2007 0
2007 3915 1
3915 133 0
133 3169 0
3169 2083 0
2083 3651 1
3651 2976 1
2976 1165 1
1165 3516 1
3516 3789 0
3789 653 1
653 208 1
208 3614 0
3614 1561 1
1561 1997 0
1997 973 1
973 365 0
365 609 0
609 1671 1
1671 1593 0
1593 2676 1
2676 1147 0
1147 ...

output:

794220612

result:

ok single line: '794220612'

Test #37:

score: 24

Accepted

time: 246ms

memory: 20844kb

input:

3962 9999 8
1 2711 0
2711 3474 1
3474 2084 0
2084 1854 0
1854 3779 1
3779 2180 0
2180 3507 0
3507 2960 1
2960 955 0
955 2600 0
2600 1585 0
1585 617 0
617 623 0
623 94 1
94 211 0
211 3649 1
3649 3123 1
3123 166 0
166 213 0
213 568 0
568 2679 1
2679 3588 1
3588 3800 1
3800 3033 1
3033 1170 1
1170 802 ...

output:

588441215

result:

ok single line: '588441215'

Test #38:

score: 24

Accepted

time: 124ms

memory: 6328kb

input:

201 7584 8
2 2 2
2 201 1
3 3 3
3 201 1
4 4 4
4 201 2
4 201 3
5 5 5
5 201 4
6 6 6
6 201 3
6 201 5
7 7 7
7 201 1
7 201 4
7 201 6
8 8 8
8 201 0
8 201 2
8 201 3
8 201 4
9 9 9
9 201 0
9 201 2
9 201 5
9 201 6
9 201 7
10 10 10
10 201 1
10 201 2
10 201 4
10 201 8
11 11 11
11 201 0
11 201 3
11 201 4
12 12 12...

output:

result:

ok single line: '1'

Test #39:

score: 24

Accepted

time: 35ms

memory: 8056kb

input:

output:

670693521

result:

ok single line: '670693521'

Test #40:

score: 24

Accepted

time: 32ms

memory: 5900kb

input:

output:

980169960

result:

ok single line: '980169960'

Test #41:

score: 24

Accepted

time: 33ms

memory: 6004kb

input:

output:

700368949

result:

ok single line: '700368949'

Test #42:

score: 24

Accepted

time: 179ms

memory: 20688kb

input:

3962 5398 8
1 1387 0
1387 3656 1
3656 1250 1
1250 128 0
128 1202 0
1202 83 1
83 90 0
90 1218 0
1218 656 0
656 565 1
565 3670 1
3670 289 0
289 239 0
239 1109 1
1109 2050 0
2050 3844 1
3844 52 0
52 1562 1
1562 3686 0
3686 2596 1
2596 3035 0
3035 1365 0
1365 943 1
943 954 1
954 560 0
560 1204 0
1204 52...

output:

338765692

result:

ok single line: '338765692'

Test #43:

score: 24

Accepted

time: 264ms

memory: 22004kb

input:

4952 8000 8
1 2814 1
2814 3322 0
3322 3360 1
3360 1222 0
1222 4598 0
4598 4852 1
4852 3052 0
3052 663 1
663 3644 1
3644 4410 0
4410 4229 1
4229 4222 1
4222 217 1
217 2528 1
2528 1136 0
1136 2144 0
2144 1118 1
1118 323 0
323 1006 1
1006 3215 0
3215 3497 1
3497 3463 1
3463 2405 0
2405 456 0
456 4819 1...

output:

result:

ok single line: '660'

Test #44:

score: 24

Accepted

time: 252ms

memory: 23932kb

input:

4952 7588 8
1 511 0
511 4170 1
4170 1735 1
1735 2956 0
2956 2305 0
2305 4126 0
4126 4565 1
4565 2701 0
2701 766 1
766 759 0
759 1530 0
1530 1952 0
1952 752 1
752 677 0
677 2739 0
2739 149 1
149 2113 0
2113 4945 0
4945 3902 1
3902 2552 1
2552 4907 0
4907 2271 1
2271 4658 0
4658 1200 0
1200 2176 1
217...

output:

13712160

result:

ok single line: '13712160'

Test #45:

score: 24

Accepted

time: 506ms

memory: 30836kb

input:

5000 10000 8
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

result:

ok single line: '4'

Test #46:

score: 24

Accepted

time: 290ms

memory: 17104kb

input:

4951 10000 8
2 3 1
3 2 1
4 5 1
5 6 1
6 4 1
7 8 1
8 9 1
9 10 1
10 7 1
11 12 1
12 13 1
13 14 1
14 15 1
15 11 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 16 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 22 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 29 1
37 38 1
38 39 1
39 40 1...

output:

result:

ok single line: '1'

Test #47:

score: 24

Accepted

time: 34ms

memory: 7880kb

input:

output:

837484870

result:

ok single line: '837484870'

Test #48:

score: 24

Accepted

time: 239ms

memory: 22096kb

input:

4952 7334 8
1 3824 0
3824 480 1
480 444 0
444 637 0
637 2312 1
2312 3356 0
3356 4210 1
4210 2721 1
2721 4781 0
4781 3785 1
3785 357 0
357 3055 0
3055 1686 0
1686 2951 0
2951 4331 0
4331 1313 1
1313 3564 1
3564 3337 0
3337 3344 1
3344 3667 0
3667 1044 0
1044 3490 1
3490 4907 0
4907 1070 0
1070 1737 1...

output:

117674516

result:

ok single line: '117674516'

Test #49:

score: 24

Accepted

time: 247ms

memory: 23916kb

input:

4952 7370 8
1 2579 1
2579 1964 1
1964 1371 1
1371 2599 0
2599 804 0
804 4618 0
4618 3004 1
3004 4230 1
4230 3411 0
3411 3143 0
3143 2458 0
2458 4734 1
4734 4628 0
4628 3284 1
3284 269 0
269 1978 0
1978 910 0
910 1989 1
1989 2327 0
2327 4011 0
4011 293 1
293 182 1
182 1070 1
1070 4505 1
4505 4870 0
4...

output:

308689785

result:

ok single line: '308689785'

Test #50:

score: 24

Accepted

time: 245ms

memory: 21980kb

input:

4952 7319 8
1 1538 0
1538 4513 0
4513 4932 0
4932 961 0
961 3337 1
3337 3413 1
3413 1373 1
1373 2702 0
2702 4299 1
4299 4938 0
4938 3207 0
3207 4694 0
4694 610 1
610 2244 1
2244 633 0
633 4800 1
4800 1007 1
1007 769 0
769 870 0
870 1555 0
1555 4758 1
4758 2327 0
2327 892 0
892 4187 0
4187 4823 0
482...

output:

506483589

result:

ok single line: '506483589'

Test #51:

score: 24

Accepted

time: 30ms

memory: 5968kb

input:

output:

result:

ok single line: '27'

Test #52:

score: 24

Accepted

time: 26ms

memory: 5888kb

input:

output:

result:

ok single line: '1728'

Test #53:

score: 24

Accepted

time: 234ms

memory: 24044kb

input:

4952 7041 8
1 59 0
59 3267 1
3267 281 0
281 1741 0
1741 661 0
661 353 1
353 1581 0
1581 2179 0
2179 170 0
170 2693 1
2693 440 0
440 3281 1
3281 3177 1
3177 4515 1
4515 3680 1
3680 4205 0
4205 216 1
216 2913 1
2913 4872 1
4872 3483 0
3483 2286 0
2286 1877 0
1877 4743 0
4743 2441 0
2441 3266 0
3266 12...

output:

result:

ok single line: '5400'

Test #54:

score: 24

Accepted

time: 30ms

memory: 5936kb

input:

output:

243354720

result:

ok single line: '243354720'

Test #55:

score: 24

Accepted

time: 34ms

memory: 5968kb

input:

output:

604422963

result:

ok single line: '604422963'

Extra Test:

score: 0

Extra Test Passed