oj.uz

Submission #522107

# Submission time Handle Problem Language Result Execution time Memory
522107 2022-02-03T20:42:46 Z blue Road Closures (APIO21_roads) C++17
100 / 100
 409 ms 166780 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int mx = 100'000;
const ll INF = 1'000'000'000'000'000'000LL;


int N;
vi U, V, W;

vi edge[mx];
vi deg(mx, 0);
vi deg_occ[mx];

vi depth(mx);
vi parent(mx, -1);

ll wt_sum = 0;

vi par_wt(mx);



void dfs1(int u, int p)
{
    for(int e: edge[u])
    {
        int v = U[e] + V[e] - u;
        int w = W[e];
        if(v == p) continue;

        par_wt[v] = w;

        depth[v] = depth[u] + 1;
        parent[v] = u;
        dfs1(v, u);
    }
}




struct segtree
{
    int l;
    int r;

    ll sm = 0;
    int ct = 0;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        sm = 0;
        ct = 0;
    }

    void insert(int v)
    {
        // cerr << "enter insert\n";
        ct++;
        sm += v;
        if(l != r)
        {
            if(v <= (l+r)/2)
            {
                if(left == NULL) left = new segtree(l, (l+r)/2);
                left->insert(v);
            }
            else
            {
                if(right == NULL) right = new segtree((l+r)/2+1, r);
                right->insert(v);
            }
        }
        // cerr << "exit insert\n";
    }

    ll getsum(ll v)
    {
        // cerr << "enter getsum\n";
        if(v == 0) 
        {
            return 0;
        }
        else if(l == r)
        {
            return ll(l) * v;
        }
        else
        {
            // cerr << "case 3\n";
            if(left != NULL && left->ct >= v) return left->getsum(v);
            else return (left == NULL ? 0 : left->sm) + right->getsum(v - (left == NULL ? 0 : left->ct));
        }
        // cerr << "exit getsum\n";
    }
};


struct DS
{
    int curr_size = 0;

    segtree S = segtree(1, 1'000'000'000);

    ll minSum(int z)
    {
        if(z > curr_size) return INF;
        else if(z <= 0) return 0;
        else return S.getsum(z);
    }

    void insert(int v)
    {
        curr_size++;
        S.insert(v);
    }

    int size()
    {
        return curr_size;
    }
};


// struct DS
// {
//     multiset<ll> values;

//     ll minSum(int z)
//     {
//         if(z > sz(values)) return INF;

//         if(z <= 0) return 0;

//         int ct = 0;
//         ll res = 0;

//         for(ll v : values)
//         {
//             res += v;
//             ct++;
//             if(ct == z) break;
//         }

//         return res;
//     }

//     void insert(ll v) 
//     {
//         values.insert(v);
//     }

//     int size()
//     {
//         return sz(values);
//     }
// };







vll minimum_closure_costs(int N_, vi U_, vi V_, vi W_)
{   
    N = N_;
    U = U_;
    V = V_;
    W = W_;

    for(int e = 0; e < N-1; e++)
    {
        edge[U[e]].push_back(e);
        edge[V[e]].push_back(e);

        deg[U[e]]++;
        deg[V[e]]++;

        wt_sum += W[e];
    }

    for(int i = 0; i < N; i++)
        deg_occ[deg[i]].push_back(i);

    for(int i = 0; i < N; i++)
    {
        sort(edge[i].begin(), edge[i].end(), [] (int e, int f)
        {
            return deg[U[e]] + deg[V[e]] > deg[U[f]] + deg[V[f]];
        });
    }


    dfs1(0, -1);

    set<pii> it_list;

    for(int i = 0; i < N; i++) it_list.insert({-depth[i], i});


    vll res(N, 0);

    res[0] = wt_sum;

                     // root deg <= K-1
    vll dp0(N), dp1(N);
    //root deg <= K

    DS extra_edges[N];

    vi intdeg = deg;
    for(int i = 1; i < N; i++)
        intdeg[i]--;

    for(int k = 1; k < N; k++)
    {
        // cerr << "\n\n\n\n\n";
        // cerr << "k = " << k << '\n';
        for(int u: deg_occ[k]) //deg_occ[0] is empty
        {
            // cerr << "eliminating " << u << '\n';
            it_list.erase({-depth[u], u});
            for(int e : edge[u])
            {
                int v = U[e] + V[e] - u;
                int w = W[e];
                if(parent[v] != u)
                    extra_edges[v].insert(w);
                // cerr << "extra edges " << v << " -> insert " << w << '\n';
            }
        }

        for(auto p: it_list)
        {
            // cerr << "\n\n";
            int u = p.second;
            // cerr << "u = " << u << '\n';

            // cerr << "ee = ";
            // for(ll y : extra_edges[u].values) cerr << y << ' ';
                // cerr << '\n';

            dp0[u] = dp1[u] = INF;

            ll basicCost = 0;

            vector<ll> upgrades;

            for(auto e: edge[u])
            {
                int v = U[e] + V[e] - u;
                ll w = W[e];

                if(v == parent[u]) continue;

                if(deg[v] <= k) break;

                basicCost += dp1[v];
                upgrades.push_back(dp0[v] + w - dp1[v]);
            }

            sort(upgrades.begin(), upgrades.end());

            ll upgrade_total = 0;

            dp0[u] = min(dp0[u], basicCost + extra_edges[u].minSum(intdeg[u] - k));
            dp1[u] = min(dp1[u], basicCost + extra_edges[u].minSum(intdeg[u] - (k-1)));

            // cerr << "pre : " << dp0[u] << ' ' << dp1[u] << '\n';

            // cerr << basicCost << '\n';

            // cerr << "ee size = " << sz(extra_edges[u]) << ", query val = " << intdeg[u] - k << '\n';




            for(int cct = 0; cct < sz(upgrades); cct++)
            {
                // cerr << "cct = " << cct << '\n';
                upgrade_total += upgrades[cct];
                dp0[u] = min(dp0[u], basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - k - (cct+1)));
                dp1[u] = min(dp1[u], basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - (k-1) - (cct+1)));
                // cerr << "! " << intdeg[u] - k - (cct+1) << ' ' << intdeg[u] - (k-1) - (cct+1) << '\n';
                // cerr << cct << " , " << basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - k - (cct+1)) << ' ' << basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - (k-1) - (cct+1)) << '\n';
            }

            if(u == 0) 
            {
                    // cerr << "adding " << dp0[u] << " a to res " << k << '\n'; 
                res[k] += dp0[u];
            }
            else if(deg[parent[u]] <= k)
            {
                // cerr << "adding " << min(dp1[u], dp0[u] + par_wt[u]) << " b to res " << k << '\n'; 
                res[k] += min(dp1[u], dp0[u] + par_wt[u]);
            }

            // cerr << u << " : " << parent[u] << ' ' << dp0[u] << ' ' << dp1[u] << '\n';
        }
    }


    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 7 ms 8908 KB Output is correct
3 Correct 7 ms 9036 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7116 KB Output is correct
6 Correct 4 ms 7116 KB Output is correct
7 Correct 4 ms 6988 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 4 ms 6988 KB Output is correct
11 Correct 3 ms 6988 KB Output is correct
12 Correct 69 ms 18500 KB Output is correct
13 Correct 120 ms 27016 KB Output is correct
14 Correct 229 ms 78108 KB Output is correct
15 Correct 270 ms 89920 KB Output is correct
16 Correct 266 ms 88172 KB Output is correct
17 Correct 126 ms 27948 KB Output is correct
18 Correct 3 ms 6896 KB Output is correct
19 Correct 102 ms 25140 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 174 ms 137908 KB Output is correct
3 Correct 195 ms 154476 KB Output is correct
4 Correct 219 ms 164612 KB Output is correct
5 Correct 185 ms 160332 KB Output is correct
6 Correct 7 ms 9648 KB Output is correct
7 Correct 7 ms 10056 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 4 ms 7116 KB Output is correct
10 Correct 4 ms 7244 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 124 ms 101644 KB Output is correct
13 Correct 194 ms 165016 KB Output is correct
14 Correct 3 ms 6860 KB Output is correct
15 Correct 175 ms 149248 KB Output is correct
16 Correct 186 ms 165012 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 3 ms 6860 KB Output is correct
3 Correct 3 ms 6860 KB Output is correct
4 Correct 4 ms 7116 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 6988 KB Output is correct
7 Correct 4 ms 7116 KB Output is correct
8 Correct 4 ms 7116 KB Output is correct
9 Correct 4 ms 7116 KB Output is correct
10 Correct 4 ms 7116 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 4 ms 7116 KB Output is correct
14 Correct 4 ms 7116 KB Output is correct
15 Correct 3 ms 6988 KB Output is correct
16 Correct 4 ms 6988 KB Output is correct
17 Correct 4 ms 7116 KB Output is correct
18 Correct 4 ms 6988 KB Output is correct
19 Correct 4 ms 6988 KB Output is correct
20 Correct 3 ms 6988 KB Output is correct
21 Correct 3 ms 6860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 3 ms 6860 KB Output is correct
3 Correct 3 ms 6860 KB Output is correct
4 Correct 4 ms 7116 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 6988 KB Output is correct
7 Correct 4 ms 7116 KB Output is correct
8 Correct 4 ms 7116 KB Output is correct
9 Correct 4 ms 7116 KB Output is correct
10 Correct 4 ms 7116 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 4 ms 7116 KB Output is correct
14 Correct 4 ms 7116 KB Output is correct
15 Correct 3 ms 6988 KB Output is correct
16 Correct 4 ms 6988 KB Output is correct
17 Correct 4 ms 7116 KB Output is correct
18 Correct 4 ms 6988 KB Output is correct
19 Correct 4 ms 6988 KB Output is correct
20 Correct 3 ms 6988 KB Output is correct
21 Correct 3 ms 6860 KB Output is correct
22 Correct 3 ms 6860 KB Output is correct
23 Correct 6 ms 8780 KB Output is correct
24 Correct 8 ms 9932 KB Output is correct
25 Correct 7 ms 8652 KB Output is correct
26 Correct 7 ms 8268 KB Output is correct
27 Correct 9 ms 9308 KB Output is correct
28 Correct 6 ms 7244 KB Output is correct
29 Correct 8 ms 9732 KB Output is correct
30 Correct 9 ms 9292 KB Output is correct
31 Correct 6 ms 7396 KB Output is correct
32 Correct 6 ms 7244 KB Output is correct
33 Correct 7 ms 9676 KB Output is correct
34 Correct 8 ms 10060 KB Output is correct
35 Correct 7 ms 9676 KB Output is correct
36 Correct 7 ms 8908 KB Output is correct
37 Correct 8 ms 9032 KB Output is correct
38 Correct 6 ms 7244 KB Output is correct
39 Correct 3 ms 6860 KB Output is correct
40 Correct 4 ms 6860 KB Output is correct
41 Correct 3 ms 7116 KB Output is correct
42 Correct 4 ms 7244 KB Output is correct
43 Correct 3 ms 6988 KB Output is correct
44 Correct 4 ms 7116 KB Output is correct
45 Correct 3 ms 7116 KB Output is correct
46 Correct 4 ms 7116 KB Output is correct
47 Correct 4 ms 7116 KB Output is correct
48 Correct 4 ms 7244 KB Output is correct
49 Correct 4 ms 7216 KB Output is correct
50 Correct 4 ms 7116 KB Output is correct
51 Correct 4 ms 7116 KB Output is correct
52 Correct 3 ms 6988 KB Output is correct
53 Correct 7 ms 8524 KB Output is correct
54 Correct 7 ms 9036 KB Output is correct
55 Correct 6 ms 7244 KB Output is correct
56 Correct 5 ms 7244 KB Output is correct
57 Correct 5 ms 7244 KB Output is correct
58 Correct 3 ms 6988 KB Output is correct
59 Correct 4 ms 7116 KB Output is correct
60 Correct 4 ms 6988 KB Output is correct
61 Correct 4 ms 6988 KB Output is correct
62 Correct 4 ms 6988 KB Output is correct
63 Correct 3 ms 6860 KB Output is correct
64 Correct 7 ms 8908 KB Output is correct
65 Correct 7 ms 8908 KB Output is correct
66 Correct 6 ms 7372 KB Output is correct
67 Correct 5 ms 7236 KB Output is correct
68 Correct 6 ms 7372 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 106432 KB Output is correct
2 Correct 326 ms 104704 KB Output is correct
3 Correct 170 ms 26736 KB Output is correct
4 Correct 339 ms 110336 KB Output is correct
5 Correct 148 ms 26848 KB Output is correct
6 Correct 135 ms 26208 KB Output is correct
7 Correct 235 ms 75436 KB Output is correct
8 Correct 117 ms 25920 KB Output is correct
9 Correct 319 ms 86784 KB Output is correct
10 Correct 317 ms 90772 KB Output is correct
11 Correct 175 ms 28184 KB Output is correct
12 Correct 122 ms 27424 KB Output is correct
13 Correct 4 ms 6948 KB Output is correct
14 Correct 171 ms 150572 KB Output is correct
15 Correct 189 ms 166312 KB Output is correct
16 Correct 7 ms 8908 KB Output is correct
17 Correct 7 ms 9016 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 6 ms 7364 KB Output is correct
20 Correct 6 ms 7372 KB Output is correct
21 Correct 102 ms 25120 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 106432 KB Output is correct
2 Correct 326 ms 104704 KB Output is correct
3 Correct 170 ms 26736 KB Output is correct
4 Correct 339 ms 110336 KB Output is correct
5 Correct 148 ms 26848 KB Output is correct
6 Correct 135 ms 26208 KB Output is correct
7 Correct 235 ms 75436 KB Output is correct
8 Correct 117 ms 25920 KB Output is correct
9 Correct 319 ms 86784 KB Output is correct
10 Correct 317 ms 90772 KB Output is correct
11 Correct 175 ms 28184 KB Output is correct
12 Correct 122 ms 27424 KB Output is correct
13 Correct 4 ms 6948 KB Output is correct
14 Correct 171 ms 150572 KB Output is correct
15 Correct 189 ms 166312 KB Output is correct
16 Correct 7 ms 8908 KB Output is correct
17 Correct 7 ms 9016 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 6 ms 7364 KB Output is correct
20 Correct 6 ms 7372 KB Output is correct
21 Correct 102 ms 25120 KB Output is correct
22 Correct 3 ms 6960 KB Output is correct
23 Correct 4 ms 6952 KB Output is correct
24 Correct 3 ms 6860 KB Output is correct
25 Correct 289 ms 99720 KB Output is correct
26 Correct 257 ms 91144 KB Output is correct
27 Correct 345 ms 115652 KB Output is correct
28 Correct 178 ms 28328 KB Output is correct
29 Correct 136 ms 26536 KB Output is correct
30 Correct 131 ms 26740 KB Output is correct
31 Correct 126 ms 27312 KB Output is correct
32 Correct 300 ms 87548 KB Output is correct
33 Correct 113 ms 26336 KB Output is correct
34 Correct 245 ms 77308 KB Output is correct
35 Correct 366 ms 97028 KB Output is correct
36 Correct 174 ms 28264 KB Output is correct
37 Correct 124 ms 27412 KB Output is correct
38 Correct 116 ms 102520 KB Output is correct
39 Correct 197 ms 166396 KB Output is correct
40 Correct 7 ms 8496 KB Output is correct
41 Correct 7 ms 9068 KB Output is correct
42 Correct 6 ms 7392 KB Output is correct
43 Correct 5 ms 7244 KB Output is correct
44 Correct 5 ms 7332 KB Output is correct
45 Correct 5 ms 6988 KB Output is correct
46 Correct 4 ms 7116 KB Output is correct
47 Correct 4 ms 7084 KB Output is correct
48 Correct 4 ms 6988 KB Output is correct
49 Correct 3 ms 6988 KB Output is correct
50 Correct 69 ms 19032 KB Output is correct
51 Correct 118 ms 27068 KB Output is correct
52 Correct 328 ms 107768 KB Output is correct
53 Correct 310 ms 105960 KB Output is correct
54 Correct 176 ms 28228 KB Output is correct
55 Correct 329 ms 111712 KB Output is correct
56 Correct 138 ms 28096 KB Output is correct
57 Correct 147 ms 27704 KB Output is correct
58 Correct 244 ms 75440 KB Output is correct
59 Correct 106 ms 25940 KB Output is correct
60 Correct 318 ms 86780 KB Output is correct
61 Correct 302 ms 90692 KB Output is correct
62 Correct 176 ms 28080 KB Output is correct
63 Correct 123 ms 27428 KB Output is correct
64 Correct 3 ms 6860 KB Output is correct
65 Correct 203 ms 150508 KB Output is correct
66 Correct 196 ms 166592 KB Output is correct
67 Correct 7 ms 8880 KB Output is correct
68 Correct 7 ms 9024 KB Output is correct
69 Correct 7 ms 7432 KB Output is correct
70 Correct 5 ms 7372 KB Output is correct
71 Correct 6 ms 7348 KB Output is correct
72 Correct 105 ms 25148 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 7 ms 8908 KB Output is correct
3 Correct 7 ms 9036 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7116 KB Output is correct
6 Correct 4 ms 7116 KB Output is correct
7 Correct 4 ms 6988 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 4 ms 6988 KB Output is correct
11 Correct 3 ms 6988 KB Output is correct
12 Correct 69 ms 18500 KB Output is correct
13 Correct 120 ms 27016 KB Output is correct
14 Correct 229 ms 78108 KB Output is correct
15 Correct 270 ms 89920 KB Output is correct
16 Correct 266 ms 88172 KB Output is correct
17 Correct 126 ms 27948 KB Output is correct
18 Correct 3 ms 6896 KB Output is correct
19 Correct 102 ms 25140 KB Output is correct
20 Correct 3 ms 6860 KB Output is correct
21 Correct 174 ms 137908 KB Output is correct
22 Correct 195 ms 154476 KB Output is correct
23 Correct 219 ms 164612 KB Output is correct
24 Correct 185 ms 160332 KB Output is correct
25 Correct 7 ms 9648 KB Output is correct
26 Correct 7 ms 10056 KB Output is correct
27 Correct 7 ms 9676 KB Output is correct
28 Correct 4 ms 7116 KB Output is correct
29 Correct 4 ms 7244 KB Output is correct
30 Correct 4 ms 7244 KB Output is correct
31 Correct 124 ms 101644 KB Output is correct
32 Correct 194 ms 165016 KB Output is correct
33 Correct 3 ms 6860 KB Output is correct
34 Correct 175 ms 149248 KB Output is correct
35 Correct 186 ms 165012 KB Output is correct
36 Correct 3 ms 6860 KB Output is correct
37 Correct 3 ms 6860 KB Output is correct
38 Correct 3 ms 6860 KB Output is correct
39 Correct 4 ms 7116 KB Output is correct
40 Correct 4 ms 7244 KB Output is correct
41 Correct 4 ms 6988 KB Output is correct
42 Correct 4 ms 7116 KB Output is correct
43 Correct 4 ms 7116 KB Output is correct
44 Correct 4 ms 7116 KB Output is correct
45 Correct 4 ms 7116 KB Output is correct
46 Correct 4 ms 7244 KB Output is correct
47 Correct 4 ms 7244 KB Output is correct
48 Correct 4 ms 7116 KB Output is correct
49 Correct 4 ms 7116 KB Output is correct
50 Correct 3 ms 6988 KB Output is correct
51 Correct 4 ms 6988 KB Output is correct
52 Correct 4 ms 7116 KB Output is correct
53 Correct 4 ms 6988 KB Output is correct
54 Correct 4 ms 6988 KB Output is correct
55 Correct 3 ms 6988 KB Output is correct
56 Correct 3 ms 6860 KB Output is correct
57 Correct 3 ms 6860 KB Output is correct
58 Correct 6 ms 8780 KB Output is correct
59 Correct 8 ms 9932 KB Output is correct
60 Correct 7 ms 8652 KB Output is correct
61 Correct 7 ms 8268 KB Output is correct
62 Correct 9 ms 9308 KB Output is correct
63 Correct 6 ms 7244 KB Output is correct
64 Correct 8 ms 9732 KB Output is correct
65 Correct 9 ms 9292 KB Output is correct
66 Correct 6 ms 7396 KB Output is correct
67 Correct 6 ms 7244 KB Output is correct
68 Correct 7 ms 9676 KB Output is correct
69 Correct 8 ms 10060 KB Output is correct
70 Correct 7 ms 9676 KB Output is correct
71 Correct 7 ms 8908 KB Output is correct
72 Correct 8 ms 9032 KB Output is correct
73 Correct 6 ms 7244 KB Output is correct
74 Correct 3 ms 6860 KB Output is correct
75 Correct 4 ms 6860 KB Output is correct
76 Correct 3 ms 7116 KB Output is correct
77 Correct 4 ms 7244 KB Output is correct
78 Correct 3 ms 6988 KB Output is correct
79 Correct 4 ms 7116 KB Output is correct
80 Correct 3 ms 7116 KB Output is correct
81 Correct 4 ms 7116 KB Output is correct
82 Correct 4 ms 7116 KB Output is correct
83 Correct 4 ms 7244 KB Output is correct
84 Correct 4 ms 7216 KB Output is correct
85 Correct 4 ms 7116 KB Output is correct
86 Correct 4 ms 7116 KB Output is correct
87 Correct 3 ms 6988 KB Output is correct
88 Correct 7 ms 8524 KB Output is correct
89 Correct 7 ms 9036 KB Output is correct
90 Correct 6 ms 7244 KB Output is correct
91 Correct 5 ms 7244 KB Output is correct
92 Correct 5 ms 7244 KB Output is correct
93 Correct 3 ms 6988 KB Output is correct
94 Correct 4 ms 7116 KB Output is correct
95 Correct 4 ms 6988 KB Output is correct
96 Correct 4 ms 6988 KB Output is correct
97 Correct 4 ms 6988 KB Output is correct
98 Correct 3 ms 6860 KB Output is correct
99 Correct 7 ms 8908 KB Output is correct
100 Correct 7 ms 8908 KB Output is correct
101 Correct 6 ms 7372 KB Output is correct
102 Correct 5 ms 7236 KB Output is correct
103 Correct 6 ms 7372 KB Output is correct
104 Correct 330 ms 106432 KB Output is correct
105 Correct 326 ms 104704 KB Output is correct
106 Correct 170 ms 26736 KB Output is correct
107 Correct 339 ms 110336 KB Output is correct
108 Correct 148 ms 26848 KB Output is correct
109 Correct 135 ms 26208 KB Output is correct
110 Correct 235 ms 75436 KB Output is correct
111 Correct 117 ms 25920 KB Output is correct
112 Correct 319 ms 86784 KB Output is correct
113 Correct 317 ms 90772 KB Output is correct
114 Correct 175 ms 28184 KB Output is correct
115 Correct 122 ms 27424 KB Output is correct
116 Correct 4 ms 6948 KB Output is correct
117 Correct 171 ms 150572 KB Output is correct
118 Correct 189 ms 166312 KB Output is correct
119 Correct 7 ms 8908 KB Output is correct
120 Correct 7 ms 9016 KB Output is correct
121 Correct 6 ms 7372 KB Output is correct
122 Correct 6 ms 7364 KB Output is correct
123 Correct 6 ms 7372 KB Output is correct
124 Correct 102 ms 25120 KB Output is correct
125 Correct 3 ms 6960 KB Output is correct
126 Correct 4 ms 6952 KB Output is correct
127 Correct 3 ms 6860 KB Output is correct
128 Correct 289 ms 99720 KB Output is correct
129 Correct 257 ms 91144 KB Output is correct
130 Correct 345 ms 115652 KB Output is correct
131 Correct 178 ms 28328 KB Output is correct
132 Correct 136 ms 26536 KB Output is correct
133 Correct 131 ms 26740 KB Output is correct
134 Correct 126 ms 27312 KB Output is correct
135 Correct 300 ms 87548 KB Output is correct
136 Correct 113 ms 26336 KB Output is correct
137 Correct 245 ms 77308 KB Output is correct
138 Correct 366 ms 97028 KB Output is correct
139 Correct 174 ms 28264 KB Output is correct
140 Correct 124 ms 27412 KB Output is correct
141 Correct 116 ms 102520 KB Output is correct
142 Correct 197 ms 166396 KB Output is correct
143 Correct 7 ms 8496 KB Output is correct
144 Correct 7 ms 9068 KB Output is correct
145 Correct 6 ms 7392 KB Output is correct
146 Correct 5 ms 7244 KB Output is correct
147 Correct 5 ms 7332 KB Output is correct
148 Correct 5 ms 6988 KB Output is correct
149 Correct 4 ms 7116 KB Output is correct
150 Correct 4 ms 7084 KB Output is correct
151 Correct 4 ms 6988 KB Output is correct
152 Correct 3 ms 6988 KB Output is correct
153 Correct 69 ms 19032 KB Output is correct
154 Correct 118 ms 27068 KB Output is correct
155 Correct 328 ms 107768 KB Output is correct
156 Correct 310 ms 105960 KB Output is correct
157 Correct 176 ms 28228 KB Output is correct
158 Correct 329 ms 111712 KB Output is correct
159 Correct 138 ms 28096 KB Output is correct
160 Correct 147 ms 27704 KB Output is correct
161 Correct 244 ms 75440 KB Output is correct
162 Correct 106 ms 25940 KB Output is correct
163 Correct 318 ms 86780 KB Output is correct
164 Correct 302 ms 90692 KB Output is correct
165 Correct 176 ms 28080 KB Output is correct
166 Correct 123 ms 27428 KB Output is correct
167 Correct 3 ms 6860 KB Output is correct
168 Correct 203 ms 150508 KB Output is correct
169 Correct 196 ms 166592 KB Output is correct
170 Correct 7 ms 8880 KB Output is correct
171 Correct 7 ms 9024 KB Output is correct
172 Correct 7 ms 7432 KB Output is correct
173 Correct 5 ms 7372 KB Output is correct
174 Correct 6 ms 7348 KB Output is correct
175 Correct 105 ms 25148 KB Output is correct
176 Correct 4 ms 6860 KB Output is correct
177 Correct 407 ms 158032 KB Output is correct
178 Correct 299 ms 126232 KB Output is correct
179 Correct 180 ms 28180 KB Output is correct
180 Correct 343 ms 122928 KB Output is correct
181 Correct 150 ms 28976 KB Output is correct
182 Correct 142 ms 28380 KB Output is correct
183 Correct 237 ms 76076 KB Output is correct
184 Correct 332 ms 106044 KB Output is correct
185 Correct 302 ms 99948 KB Output is correct
186 Correct 295 ms 93892 KB Output is correct
187 Correct 285 ms 85848 KB Output is correct
188 Correct 325 ms 107744 KB Output is correct
189 Correct 315 ms 89556 KB Output is correct
190 Correct 409 ms 116136 KB Output is correct
191 Correct 175 ms 28092 KB Output is correct
192 Correct 284 ms 85176 KB Output is correct
193 Correct 305 ms 100716 KB Output is correct
194 Correct 189 ms 29008 KB Output is correct
195 Correct 177 ms 139684 KB Output is correct
196 Correct 199 ms 156500 KB Output is correct
197 Correct 226 ms 166780 KB Output is correct
198 Correct 189 ms 162604 KB Output is correct
199 Correct 7 ms 8756 KB Output is correct
200 Correct 9 ms 10044 KB Output is correct
201 Correct 7 ms 8780 KB Output is correct
202 Correct 7 ms 8240 KB Output is correct
203 Correct 9 ms 9308 KB Output is correct
204 Correct 6 ms 7356 KB Output is correct
205 Correct 9 ms 9660 KB Output is correct
206 Correct 9 ms 9320 KB Output is correct
207 Correct 6 ms 7352 KB Output is correct
208 Correct 6 ms 7364 KB Output is correct
209 Correct 7 ms 9668 KB Output is correct
210 Correct 8 ms 10052 KB Output is correct
211 Correct 7 ms 9680 KB Output is correct
212 Correct 7 ms 8888 KB Output is correct
213 Correct 8 ms 9036 KB Output is correct
214 Correct 6 ms 7372 KB Output is correct
215 Correct 4 ms 6956 KB Output is correct
216 Correct 3 ms 6860 KB Output is correct
217 Correct 4 ms 7116 KB Output is correct
218 Correct 4 ms 7200 KB Output is correct
219 Correct 4 ms 6988 KB Output is correct
220 Correct 4 ms 7116 KB Output is correct
221 Correct 4 ms 7116 KB Output is correct
222 Correct 4 ms 7116 KB Output is correct
223 Correct 4 ms 7216 KB Output is correct
224 Correct 4 ms 7216 KB Output is correct
225 Correct 4 ms 7212 KB Output is correct
226 Correct 4 ms 7116 KB Output is correct
227 Correct 4 ms 7116 KB Output is correct
228 Correct 4 ms 6960 KB Output is correct
229 Correct 297 ms 99936 KB Output is correct
230 Correct 275 ms 91056 KB Output is correct
231 Correct 358 ms 115760 KB Output is correct
232 Correct 188 ms 28228 KB Output is correct
233 Correct 134 ms 26432 KB Output is correct
234 Correct 133 ms 26816 KB Output is correct
235 Correct 136 ms 27292 KB Output is correct
236 Correct 291 ms 87488 KB Output is correct
237 Correct 117 ms 26424 KB Output is correct
238 Correct 248 ms 77336 KB Output is correct
239 Correct 369 ms 97024 KB Output is correct
240 Correct 184 ms 28188 KB Output is correct
241 Correct 126 ms 27432 KB Output is correct
242 Correct 116 ms 102484 KB Output is correct
243 Correct 205 ms 166336 KB Output is correct
244 Correct 6 ms 8500 KB Output is correct
245 Correct 7 ms 9016 KB Output is correct
246 Correct 6 ms 7372 KB Output is correct
247 Correct 5 ms 7220 KB Output is correct
248 Correct 6 ms 7356 KB Output is correct
249 Correct 4 ms 6988 KB Output is correct
250 Correct 5 ms 7116 KB Output is correct
251 Correct 4 ms 6988 KB Output is correct
252 Correct 4 ms 6988 KB Output is correct
253 Correct 5 ms 6988 KB Output is correct
254 Correct 75 ms 19100 KB Output is correct
255 Correct 118 ms 27072 KB Output is correct
256 Correct 232 ms 78016 KB Output is correct
257 Correct 301 ms 89808 KB Output is correct
258 Correct 270 ms 88124 KB Output is correct
259 Correct 131 ms 27948 KB Output is correct
260 Correct 325 ms 107680 KB Output is correct
261 Correct 328 ms 106076 KB Output is correct
262 Correct 171 ms 28100 KB Output is correct
263 Correct 336 ms 111720 KB Output is correct
264 Correct 147 ms 28072 KB Output is correct
265 Correct 135 ms 27576 KB Output is correct
266 Correct 238 ms 75360 KB Output is correct
267 Correct 131 ms 25916 KB Output is correct
268 Correct 322 ms 86668 KB Output is correct
269 Correct 316 ms 90772 KB Output is correct
270 Correct 165 ms 28188 KB Output is correct
271 Correct 126 ms 27436 KB Output is correct
272 Correct 4 ms 6860 KB Output is correct
273 Correct 188 ms 150628 KB Output is correct
274 Correct 194 ms 166308 KB Output is correct
275 Correct 7 ms 8908 KB Output is correct
276 Correct 8 ms 9020 KB Output is correct
277 Correct 6 ms 7372 KB Output is correct
278 Correct 6 ms 7348 KB Output is correct
279 Correct 7 ms 7360 KB Output is correct
280 Correct 104 ms 25196 KB Output is correct