oj.uz

답안 #802739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802739 2023-08-02T13:50:30 Z SamAnd 분수 공원 (IOI21_parks) C++17
70 / 100
 1643 ms 135660 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 400005;

int n;
vector<int> g[N];

bool c[N];
vector<int> uu, vv;
void dfs(int x)
{
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (c[h])
            continue;
        uu.push_back(x);
        vv.push_back(g[x][i]);
        dfs(h);
    }
}

vector<pair<int, int> > rs;
vector<int> gg[N], gi[N];
void dfs(int x, vector<int>& a, vector<int>& b)
{
    c[x] = true;
    for (int i = 0; i < gg[x].size(); ++i)
    {
        int h = gg[x][i];
        if (a[gi[x][i]] == -1)
        {
            a[gi[x][i]] = rs[x].fi;
            b[gi[x][i]] = rs[x].se;
        }
        if (!c[h])
            dfs(h, a, b);
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    std::vector<int> u, v, a, b;

    n = sz(x);
    vector<pair<int, int> > p;
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; ++i)
    {
        p.push_back(m_p(x[i], y[i]));
        mp[m_p(x[i], y[i])] = i;
    }

    int z = 0;
    map<pair<int, int>, int> s;
    for (int i = 0; i < n; ++i)
    {
        int x = p[i].fi;
        int y = p[i].se;
        if (mp.find(m_p(x + 2, y)) != mp.end())
        {
            u.push_back(mp[m_p(x, y)]);
            v.push_back(mp[m_p(x + 2, y)]);
            if (s.find(m_p(x + 1, y + 1)) == s.end())
                s[m_p(x + 1, y + 1)] = z++;
            if (s.find(m_p(x + 1, y - 1)) == s.end())
                s[m_p(x + 1, y - 1)] = z++;
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
            gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x + 1, y - 1)]);
            gg[s[m_p(x + 1, y - 1)]].push_back(s[m_p(x + 1, y + 1)]);
            gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
            gi[s[m_p(x + 1, y - 1)]].push_back(sz(u) - 1);
        }
        if (mp.find(m_p(x, y + 2)) != mp.end())
        {
            u.push_back(mp[m_p(x, y)]);
            v.push_back(mp[m_p(x, y + 2)]);
            if (s.find(m_p(x + 1, y + 1)) == s.end())
                s[m_p(x + 1, y + 1)] = z++;
            if (s.find(m_p(x - 1, y + 1)) == s.end())
                s[m_p(x - 1, y + 1)] = z++;
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
            gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x - 1, y + 1)]);
            gg[s[m_p(x - 1, y + 1)]].push_back(s[m_p(x + 1, y + 1)]);
            gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
            gi[s[m_p(x - 1, y + 1)]].push_back(sz(u) - 1);
        }
    }

    rs.assign(z, m_p(0, 0));
    for (auto it = s.begin(); it != s.end(); ++it)
    {
        rs[it->se] = it->fi;
    }

    dfs(0);
    for (int i = 0; i < n; ++i)
    {
        if (!c[i])
            return 0;
    }

    int maxu = 0;
    for (int i = 0; i < n; ++i)
    {
        maxu = max(maxu, x[i]);
    }

    memset(c, false, sizeof c);
    a.assign(sz(u), -1);
    b.assign(sz(u), -1);

    if (maxu <= 6)
    {
        u = uu;
        v = vv;
        a.assign(sz(u), -1);
        b.assign(sz(u), -1);
        vector<pair<pair<int, int>, int> > p;
        for (int i = 0; i < sz(u); ++i)
        {
            int mx = (x[u[i]] + x[v[i]]) / 2;
            int my = (y[u[i]] + y[v[i]]) / 2;
            p.push_back(m_p(m_p(mx, my), i));
        }
        sort(all(p));
        for (int i = 0; i < sz(u); ++i)
        {
            uu[i] = u[p[i].se];
            vv[i] = v[p[i].se];
        }
        u = uu;
        v = vv;
        for (int i = 0; i < sz(u); ++i)
        {
            int mx = (x[u[i]] + x[v[i]]) / 2;
            int my = (y[u[i]] + y[v[i]]) / 2;
            if (mx % 2 == 0)
            {
                if (!c[s[m_p(mx - 1, my)]])
                {
                    a[i] = mx - 1;
                    b[i] = my;
                    c[s[m_p(mx - 1, my)]] = true;
                }
                else
                {
                    assert(!c[s[m_p(mx + 1, my)]]);
                    a[i] = mx + 1;
                    b[i] = my;
                    c[s[m_p(mx + 1, my)]] = true;
                }
            }
            else
            {
                assert(my % 2 == 0);
                if (!c[s[m_p(mx, my - 1)]])
                {
                    a[i] = mx;
                    b[i] = my - 1;
                    c[s[m_p(mx, my - 1)]] = true;
                }
                else
                {
                    assert(!c[s[m_p(mx, my + 1)]]);
                    a[i] = mx;
                    b[i] = my + 1;
                    c[s[m_p(mx, my + 1)]] = true;
                }
            }
        }
    }
    else
    {
        for (int i = 0; i < z; ++i)
        {
            if (!c[i] && sz(gg[i]) == 1)
            {
                dfs(i, a, b);
            }
        }
        for (int i = 0; i < z; ++i)
        {
            if (!c[i])
            {
                dfs(i, a, b);
            }
        }
    }

    build(u, v, a, b);
    return 1;
}

/*
3
2 2
4 4
2 4

3
2 2
4 2
2 4

3
4 2
2 2
4 4

3
4 4
4 2
2 4

9
4 2
4 4
2 2
2 4
2 6
4 6
2 8
4 8
4 10
*/

Compilation message

parks.cpp: In function 'void dfs(int)':
parks.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
parks.cpp: In function 'void dfs(int, std::vector<int>&, std::vector<int>&)':
parks.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < gg[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 14 ms 28756 KB Output is correct
3 Correct 14 ms 28372 KB Output is correct
4 Correct 13 ms 28756 KB Output is correct
5 Correct 13 ms 28860 KB Output is correct
6 Correct 13 ms 28392 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28484 KB Output is correct
9 Correct 518 ms 80784 KB Output is correct
10 Correct 34 ms 34128 KB Output is correct
11 Correct 170 ms 57036 KB Output is correct
12 Correct 55 ms 36768 KB Output is correct
13 Correct 118 ms 48412 KB Output is correct
14 Correct 16 ms 28808 KB Output is correct
15 Correct 19 ms 29268 KB Output is correct
16 Correct 511 ms 77588 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 14 ms 28756 KB Output is correct
3 Correct 14 ms 28372 KB Output is correct
4 Correct 13 ms 28756 KB Output is correct
5 Correct 13 ms 28860 KB Output is correct
6 Correct 13 ms 28392 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28484 KB Output is correct
9 Correct 518 ms 80784 KB Output is correct
10 Correct 34 ms 34128 KB Output is correct
11 Correct 170 ms 57036 KB Output is correct
12 Correct 55 ms 36768 KB Output is correct
13 Correct 118 ms 48412 KB Output is correct
14 Correct 16 ms 28808 KB Output is correct
15 Correct 19 ms 29268 KB Output is correct
16 Correct 511 ms 77588 KB Output is correct
17 Correct 14 ms 28756 KB Output is correct
18 Correct 13 ms 28824 KB Output is correct
19 Correct 14 ms 28852 KB Output is correct
20 Correct 14 ms 28756 KB Output is correct
21 Correct 13 ms 28372 KB Output is correct
22 Correct 14 ms 28816 KB Output is correct
23 Correct 1492 ms 115360 KB Output is correct
24 Correct 16 ms 28756 KB Output is correct
25 Correct 19 ms 29336 KB Output is correct
26 Correct 21 ms 29524 KB Output is correct
27 Correct 25 ms 29732 KB Output is correct
28 Correct 465 ms 64320 KB Output is correct
29 Correct 781 ms 80804 KB Output is correct
30 Correct 1128 ms 100428 KB Output is correct
31 Correct 1520 ms 114364 KB Output is correct
32 Correct 14 ms 28756 KB Output is correct
33 Correct 14 ms 28816 KB Output is correct
34 Correct 13 ms 28752 KB Output is correct
35 Correct 13 ms 28436 KB Output is correct
36 Correct 13 ms 28372 KB Output is correct
37 Correct 13 ms 28756 KB Output is correct
38 Correct 16 ms 28756 KB Output is correct
39 Correct 14 ms 28756 KB Output is correct
40 Correct 14 ms 28816 KB Output is correct
41 Correct 13 ms 28372 KB Output is correct
42 Correct 15 ms 28824 KB Output is correct
43 Correct 17 ms 29136 KB Output is correct
44 Correct 19 ms 29376 KB Output is correct
45 Correct 483 ms 70160 KB Output is correct
46 Correct 804 ms 88880 KB Output is correct
47 Correct 821 ms 88380 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 14 ms 28756 KB Output is correct
3 Correct 14 ms 28372 KB Output is correct
4 Correct 13 ms 28756 KB Output is correct
5 Correct 13 ms 28860 KB Output is correct
6 Correct 13 ms 28392 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28484 KB Output is correct
9 Correct 518 ms 80784 KB Output is correct
10 Correct 34 ms 34128 KB Output is correct
11 Correct 170 ms 57036 KB Output is correct
12 Correct 55 ms 36768 KB Output is correct
13 Correct 118 ms 48412 KB Output is correct
14 Correct 16 ms 28808 KB Output is correct
15 Correct 19 ms 29268 KB Output is correct
16 Correct 511 ms 77588 KB Output is correct
17 Correct 14 ms 28756 KB Output is correct
18 Correct 13 ms 28824 KB Output is correct
19 Correct 14 ms 28852 KB Output is correct
20 Correct 14 ms 28756 KB Output is correct
21 Correct 13 ms 28372 KB Output is correct
22 Correct 14 ms 28816 KB Output is correct
23 Correct 1492 ms 115360 KB Output is correct
24 Correct 16 ms 28756 KB Output is correct
25 Correct 19 ms 29336 KB Output is correct
26 Correct 21 ms 29524 KB Output is correct
27 Correct 25 ms 29732 KB Output is correct
28 Correct 465 ms 64320 KB Output is correct
29 Correct 781 ms 80804 KB Output is correct
30 Correct 1128 ms 100428 KB Output is correct
31 Correct 1520 ms 114364 KB Output is correct
32 Correct 14 ms 28756 KB Output is correct
33 Correct 14 ms 28816 KB Output is correct
34 Correct 13 ms 28752 KB Output is correct
35 Correct 13 ms 28436 KB Output is correct
36 Correct 13 ms 28372 KB Output is correct
37 Correct 13 ms 28756 KB Output is correct
38 Correct 16 ms 28756 KB Output is correct
39 Correct 14 ms 28756 KB Output is correct
40 Correct 14 ms 28816 KB Output is correct
41 Correct 13 ms 28372 KB Output is correct
42 Correct 15 ms 28824 KB Output is correct
43 Correct 17 ms 29136 KB Output is correct
44 Correct 19 ms 29376 KB Output is correct
45 Correct 483 ms 70160 KB Output is correct
46 Correct 804 ms 88880 KB Output is correct
47 Correct 821 ms 88380 KB Output is correct
48 Correct 14 ms 28756 KB Output is correct
49 Correct 16 ms 28756 KB Output is correct
50 Correct 14 ms 28756 KB Output is correct
51 Correct 14 ms 28864 KB Output is correct
52 Correct 14 ms 28748 KB Output is correct
53 Correct 14 ms 28756 KB Output is correct
54 Correct 14 ms 28756 KB Output is correct
55 Correct 1643 ms 108076 KB Output is correct
56 Correct 13 ms 28756 KB Output is correct
57 Correct 19 ms 29588 KB Output is correct
58 Correct 35 ms 31444 KB Output is correct
59 Correct 42 ms 31684 KB Output is correct
60 Correct 630 ms 71012 KB Output is correct
61 Correct 1008 ms 85624 KB Output is correct
62 Correct 1225 ms 96220 KB Output is correct
63 Correct 1627 ms 109788 KB Output is correct
64 Correct 14 ms 28372 KB Output is correct
65 Correct 14 ms 28756 KB Output is correct
66 Correct 14 ms 28372 KB Output is correct
67 Correct 1147 ms 130980 KB Output is correct
68 Correct 1176 ms 131296 KB Output is correct
69 Correct 1233 ms 132564 KB Output is correct
70 Correct 21 ms 29780 KB Output is correct
71 Correct 33 ms 30924 KB Output is correct
72 Correct 492 ms 67968 KB Output is correct
73 Correct 875 ms 89400 KB Output is correct
74 Correct 1202 ms 107628 KB Output is correct
75 Correct 1430 ms 119848 KB Output is correct
76 Correct 1142 ms 135660 KB Output is correct
77 Correct 31 ms 30272 KB Output is correct
78 Correct 35 ms 31624 KB Output is correct
79 Correct 564 ms 70376 KB Output is correct
80 Correct 962 ms 91552 KB Output is correct
81 Correct 1295 ms 113488 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 14 ms 28756 KB Output is correct
3 Correct 14 ms 28372 KB Output is correct
4 Correct 13 ms 28756 KB Output is correct
5 Correct 13 ms 28860 KB Output is correct
6 Correct 13 ms 28392 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28484 KB Output is correct
9 Correct 518 ms 80784 KB Output is correct
10 Correct 34 ms 34128 KB Output is correct
11 Correct 170 ms 57036 KB Output is correct
12 Correct 55 ms 36768 KB Output is correct
13 Correct 118 ms 48412 KB Output is correct
14 Correct 16 ms 28808 KB Output is correct
15 Correct 19 ms 29268 KB Output is correct
16 Correct 511 ms 77588 KB Output is correct
17 Correct 15 ms 28756 KB Output is correct
18 Correct 15 ms 28852 KB Output is correct
19 Correct 14 ms 28372 KB Output is correct
20 Correct 994 ms 108116 KB Output is correct
21 Correct 1097 ms 104640 KB Output is correct
22 Correct 997 ms 102792 KB Output is correct
23 Correct 904 ms 113224 KB Output is correct
24 Correct 227 ms 45656 KB Output is correct
25 Correct 1010 ms 106840 KB Output is correct
26 Correct 1044 ms 107124 KB Output is correct
27 Correct 1221 ms 118200 KB Output is correct
28 Correct 1158 ms 118204 KB Output is correct
29 Correct 1148 ms 118264 KB Output is correct
30 Correct 1174 ms 118212 KB Output is correct
31 Correct 14 ms 28756 KB Output is correct
32 Correct 57 ms 34356 KB Output is correct
33 Correct 86 ms 37128 KB Output is correct
34 Correct 1051 ms 108292 KB Output is correct
35 Correct 38 ms 31388 KB Output is correct
36 Correct 185 ms 42964 KB Output is correct
37 Correct 421 ms 57156 KB Output is correct
38 Correct 399 ms 56316 KB Output is correct
39 Correct 548 ms 66624 KB Output is correct
40 Correct 732 ms 77256 KB Output is correct
41 Correct 978 ms 86840 KB Output is correct
42 Correct 1196 ms 97712 KB Output is correct
43 Correct 14 ms 28800 KB Output is correct
44 Correct 16 ms 28756 KB Output is correct
45 Correct 14 ms 28756 KB Output is correct
46 Correct 14 ms 28372 KB Output is correct
47 Correct 14 ms 28472 KB Output is correct
48 Correct 14 ms 28860 KB Output is correct
49 Correct 14 ms 28744 KB Output is correct
50 Correct 15 ms 28780 KB Output is correct
51 Correct 14 ms 28832 KB Output is correct
52 Correct 14 ms 28372 KB Output is correct
53 Correct 14 ms 28756 KB Output is correct
54 Correct 19 ms 29144 KB Output is correct
55 Correct 20 ms 29412 KB Output is correct
56 Correct 509 ms 70244 KB Output is correct
57 Correct 821 ms 89056 KB Output is correct
58 Correct 811 ms 88480 KB Output is correct
59 Correct 14 ms 28372 KB Output is correct
60 Correct 15 ms 28756 KB Output is correct
61 Correct 14 ms 28460 KB Output is correct
62 Correct 1167 ms 129388 KB Output is correct
63 Correct 1377 ms 129636 KB Output is correct
64 Correct 1364 ms 130868 KB Output is correct
65 Correct 23 ms 29780 KB Output is correct
66 Correct 41 ms 30932 KB Output is correct
67 Correct 575 ms 67316 KB Output is correct
68 Correct 883 ms 88232 KB Output is correct
69 Correct 1251 ms 105792 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 14 ms 28756 KB Output is correct
3 Correct 14 ms 28372 KB Output is correct
4 Correct 13 ms 28756 KB Output is correct
5 Correct 13 ms 28860 KB Output is correct
6 Correct 13 ms 28392 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28484 KB Output is correct
9 Correct 518 ms 80784 KB Output is correct
10 Correct 34 ms 34128 KB Output is correct
11 Correct 170 ms 57036 KB Output is correct
12 Correct 55 ms 36768 KB Output is correct
13 Correct 118 ms 48412 KB Output is correct
14 Correct 16 ms 28808 KB Output is correct
15 Correct 19 ms 29268 KB Output is correct
16 Correct 511 ms 77588 KB Output is correct
17 Correct 1101 ms 134232 KB Output is correct
18 Correct 1137 ms 128112 KB Output is correct
19 Correct 1044 ms 107924 KB Output is correct
20 Correct 1429 ms 108000 KB Output is correct
21 Correct 1102 ms 107728 KB Output is correct
22 Correct 14 ms 28756 KB Output is correct
23 Correct 124 ms 40496 KB Output is correct
24 Correct 72 ms 34832 KB Output is correct
25 Correct 330 ms 49840 KB Output is correct
26 Correct 613 ms 65324 KB Output is correct
27 Correct 568 ms 68772 KB Output is correct
28 Correct 740 ms 76412 KB Output is correct
29 Correct 993 ms 89096 KB Output is correct
30 Correct 1146 ms 98684 KB Output is correct
31 Correct 1390 ms 107628 KB Output is correct
32 Correct 1428 ms 118316 KB Output is correct
33 Correct 1187 ms 133880 KB Output is correct
34 Correct 25 ms 30204 KB Output is correct
35 Correct 35 ms 31504 KB Output is correct
36 Correct 537 ms 69628 KB Output is correct
37 Correct 934 ms 90280 KB Output is correct
38 Correct 1312 ms 111784 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 14 ms 28756 KB Output is correct
3 Correct 14 ms 28372 KB Output is correct
4 Correct 13 ms 28756 KB Output is correct
5 Correct 13 ms 28860 KB Output is correct
6 Correct 13 ms 28392 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28484 KB Output is correct
9 Correct 518 ms 80784 KB Output is correct
10 Correct 34 ms 34128 KB Output is correct
11 Correct 170 ms 57036 KB Output is correct
12 Correct 55 ms 36768 KB Output is correct
13 Correct 118 ms 48412 KB Output is correct
14 Correct 16 ms 28808 KB Output is correct
15 Correct 19 ms 29268 KB Output is correct
16 Correct 511 ms 77588 KB Output is correct
17 Correct 14 ms 28756 KB Output is correct
18 Correct 13 ms 28824 KB Output is correct
19 Correct 14 ms 28852 KB Output is correct
20 Correct 14 ms 28756 KB Output is correct
21 Correct 13 ms 28372 KB Output is correct
22 Correct 14 ms 28816 KB Output is correct
23 Correct 1492 ms 115360 KB Output is correct
24 Correct 16 ms 28756 KB Output is correct
25 Correct 19 ms 29336 KB Output is correct
26 Correct 21 ms 29524 KB Output is correct
27 Correct 25 ms 29732 KB Output is correct
28 Correct 465 ms 64320 KB Output is correct
29 Correct 781 ms 80804 KB Output is correct
30 Correct 1128 ms 100428 KB Output is correct
31 Correct 1520 ms 114364 KB Output is correct
32 Correct 14 ms 28756 KB Output is correct
33 Correct 14 ms 28816 KB Output is correct
34 Correct 13 ms 28752 KB Output is correct
35 Correct 13 ms 28436 KB Output is correct
36 Correct 13 ms 28372 KB Output is correct
37 Correct 13 ms 28756 KB Output is correct
38 Correct 16 ms 28756 KB Output is correct
39 Correct 14 ms 28756 KB Output is correct
40 Correct 14 ms 28816 KB Output is correct
41 Correct 13 ms 28372 KB Output is correct
42 Correct 15 ms 28824 KB Output is correct
43 Correct 17 ms 29136 KB Output is correct
44 Correct 19 ms 29376 KB Output is correct
45 Correct 483 ms 70160 KB Output is correct
46 Correct 804 ms 88880 KB Output is correct
47 Correct 821 ms 88380 KB Output is correct
48 Correct 14 ms 28756 KB Output is correct
49 Correct 16 ms 28756 KB Output is correct
50 Correct 14 ms 28756 KB Output is correct
51 Correct 14 ms 28864 KB Output is correct
52 Correct 14 ms 28748 KB Output is correct
53 Correct 14 ms 28756 KB Output is correct
54 Correct 14 ms 28756 KB Output is correct
55 Correct 1643 ms 108076 KB Output is correct
56 Correct 13 ms 28756 KB Output is correct
57 Correct 19 ms 29588 KB Output is correct
58 Correct 35 ms 31444 KB Output is correct
59 Correct 42 ms 31684 KB Output is correct
60 Correct 630 ms 71012 KB Output is correct
61 Correct 1008 ms 85624 KB Output is correct
62 Correct 1225 ms 96220 KB Output is correct
63 Correct 1627 ms 109788 KB Output is correct
64 Correct 14 ms 28372 KB Output is correct
65 Correct 14 ms 28756 KB Output is correct
66 Correct 14 ms 28372 KB Output is correct
67 Correct 1147 ms 130980 KB Output is correct
68 Correct 1176 ms 131296 KB Output is correct
69 Correct 1233 ms 132564 KB Output is correct
70 Correct 21 ms 29780 KB Output is correct
71 Correct 33 ms 30924 KB Output is correct
72 Correct 492 ms 67968 KB Output is correct
73 Correct 875 ms 89400 KB Output is correct
74 Correct 1202 ms 107628 KB Output is correct
75 Correct 1430 ms 119848 KB Output is correct
76 Correct 1142 ms 135660 KB Output is correct
77 Correct 31 ms 30272 KB Output is correct
78 Correct 35 ms 31624 KB Output is correct
79 Correct 564 ms 70376 KB Output is correct
80 Correct 962 ms 91552 KB Output is correct
81 Correct 1295 ms 113488 KB Output is correct
82 Correct 15 ms 28756 KB Output is correct
83 Correct 15 ms 28852 KB Output is correct
84 Correct 14 ms 28372 KB Output is correct
85 Correct 994 ms 108116 KB Output is correct
86 Correct 1097 ms 104640 KB Output is correct
87 Correct 997 ms 102792 KB Output is correct
88 Correct 904 ms 113224 KB Output is correct
89 Correct 227 ms 45656 KB Output is correct
90 Correct 1010 ms 106840 KB Output is correct
91 Correct 1044 ms 107124 KB Output is correct
92 Correct 1221 ms 118200 KB Output is correct
93 Correct 1158 ms 118204 KB Output is correct
94 Correct 1148 ms 118264 KB Output is correct
95 Correct 1174 ms 118212 KB Output is correct
96 Correct 14 ms 28756 KB Output is correct
97 Correct 57 ms 34356 KB Output is correct
98 Correct 86 ms 37128 KB Output is correct
99 Correct 1051 ms 108292 KB Output is correct
100 Correct 38 ms 31388 KB Output is correct
101 Correct 185 ms 42964 KB Output is correct
102 Correct 421 ms 57156 KB Output is correct
103 Correct 399 ms 56316 KB Output is correct
104 Correct 548 ms 66624 KB Output is correct
105 Correct 732 ms 77256 KB Output is correct
106 Correct 978 ms 86840 KB Output is correct
107 Correct 1196 ms 97712 KB Output is correct
108 Correct 14 ms 28800 KB Output is correct
109 Correct 16 ms 28756 KB Output is correct
110 Correct 14 ms 28756 KB Output is correct
111 Correct 14 ms 28372 KB Output is correct
112 Correct 14 ms 28472 KB Output is correct
113 Correct 14 ms 28860 KB Output is correct
114 Correct 14 ms 28744 KB Output is correct
115 Correct 15 ms 28780 KB Output is correct
116 Correct 14 ms 28832 KB Output is correct
117 Correct 14 ms 28372 KB Output is correct
118 Correct 14 ms 28756 KB Output is correct
119 Correct 19 ms 29144 KB Output is correct
120 Correct 20 ms 29412 KB Output is correct
121 Correct 509 ms 70244 KB Output is correct
122 Correct 821 ms 89056 KB Output is correct
123 Correct 811 ms 88480 KB Output is correct
124 Correct 14 ms 28372 KB Output is correct
125 Correct 15 ms 28756 KB Output is correct
126 Correct 14 ms 28460 KB Output is correct
127 Correct 1167 ms 129388 KB Output is correct
128 Correct 1377 ms 129636 KB Output is correct
129 Correct 1364 ms 130868 KB Output is correct
130 Correct 23 ms 29780 KB Output is correct
131 Correct 41 ms 30932 KB Output is correct
132 Correct 575 ms 67316 KB Output is correct
133 Correct 883 ms 88232 KB Output is correct
134 Correct 1251 ms 105792 KB Output is correct
135 Correct 1101 ms 134232 KB Output is correct
136 Correct 1137 ms 128112 KB Output is correct
137 Correct 1044 ms 107924 KB Output is correct
138 Correct 1429 ms 108000 KB Output is correct
139 Correct 1102 ms 107728 KB Output is correct
140 Correct 14 ms 28756 KB Output is correct
141 Correct 124 ms 40496 KB Output is correct
142 Correct 72 ms 34832 KB Output is correct
143 Correct 330 ms 49840 KB Output is correct
144 Correct 613 ms 65324 KB Output is correct
145 Correct 568 ms 68772 KB Output is correct
146 Correct 740 ms 76412 KB Output is correct
147 Correct 993 ms 89096 KB Output is correct
148 Correct 1146 ms 98684 KB Output is correct
149 Correct 1390 ms 107628 KB Output is correct
150 Correct 1428 ms 118316 KB Output is correct
151 Correct 1187 ms 133880 KB Output is correct
152 Correct 25 ms 30204 KB Output is correct
153 Correct 35 ms 31504 KB Output is correct
154 Correct 537 ms 69628 KB Output is correct
155 Correct 934 ms 90280 KB Output is correct
156 Correct 1312 ms 111784 KB Output is correct
157 Correct 15 ms 28800 KB Output is correct
158 Correct 16 ms 28484 KB Output is correct
159 Incorrect 14 ms 28756 KB Tree @(199999, 3) appears more than once: for edges on positions 1 and 2
160 Halted 0 ms 0 KB -