oj.uz

답안 #522108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522108 2022-02-03T20:45:49 Z blue 도로 폐쇄 (APIO21_roads) C++17
100 / 100
 422 ms 165708 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;
    }
};
 
 
 
 
 
 
 
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]);
            }
        }
    }
 
 
    return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 8 ms 8908 KB Output is correct
3 Correct 10 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 3 ms 6988 KB Output is correct
11 Correct 4 ms 6988 KB Output is correct
12 Correct 70 ms 18504 KB Output is correct
13 Correct 120 ms 26784 KB Output is correct
14 Correct 242 ms 77208 KB Output is correct
15 Correct 279 ms 88652 KB Output is correct
16 Correct 267 ms 87100 KB Output is correct
17 Correct 125 ms 26788 KB Output is correct
18 Correct 3 ms 6860 KB Output is correct
19 Correct 105 ms 24872 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6860 KB Output is correct
2 Correct 176 ms 137896 KB Output is correct
3 Correct 197 ms 154576 KB Output is correct
4 Correct 235 ms 164648 KB Output is correct
5 Correct 187 ms 160300 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 10 ms 10020 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 121 ms 101608 KB Output is correct
13 Correct 190 ms 165048 KB Output is correct
14 Correct 4 ms 6844 KB Output is correct
15 Correct 174 ms 149592 KB Output is correct
16 Correct 194 ms 165036 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 5 ms 7116 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 6980 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 7216 KB Output is correct
10 Correct 5 ms 7236 KB Output is correct
11 Correct 6 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 5 ms 7116 KB Output is correct
14 Correct 5 ms 7116 KB Output is correct
15 Correct 4 ms 6988 KB Output is correct
16 Correct 4 ms 6988 KB Output is correct
17 Correct 4 ms 7080 KB Output is correct
18 Correct 4 ms 6988 KB Output is correct
19 Correct 4 ms 6960 KB Output is correct
20 Correct 4 ms 6956 KB Output is correct
21 Correct 3 ms 6860 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 5 ms 7116 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 6980 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 7216 KB Output is correct
10 Correct 5 ms 7236 KB Output is correct
11 Correct 6 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 5 ms 7116 KB Output is correct
14 Correct 5 ms 7116 KB Output is correct
15 Correct 4 ms 6988 KB Output is correct
16 Correct 4 ms 6988 KB Output is correct
17 Correct 4 ms 7080 KB Output is correct
18 Correct 4 ms 6988 KB Output is correct
19 Correct 4 ms 6960 KB Output is correct
20 Correct 4 ms 6956 KB Output is correct
21 Correct 3 ms 6860 KB Output is correct
22 Correct 4 ms 6860 KB Output is correct
23 Correct 7 ms 8760 KB Output is correct
24 Correct 10 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 12 ms 9276 KB Output is correct
28 Correct 7 ms 7488 KB Output is correct
29 Correct 9 ms 9668 KB Output is correct
30 Correct 10 ms 9272 KB Output is correct
31 Correct 7 ms 7372 KB Output is correct
32 Correct 6 ms 7372 KB Output is correct
33 Correct 7 ms 9676 KB Output is correct
34 Correct 8 ms 10048 KB Output is correct
35 Correct 8 ms 9648 KB Output is correct
36 Correct 7 ms 8908 KB Output is correct
37 Correct 8 ms 9088 KB Output is correct
38 Correct 5 ms 7372 KB Output is correct
39 Correct 4 ms 6860 KB Output is correct
40 Correct 3 ms 6860 KB Output is correct
41 Correct 4 ms 7116 KB Output is correct
42 Correct 4 ms 7212 KB Output is correct
43 Correct 4 ms 6988 KB Output is correct
44 Correct 5 ms 7188 KB Output is correct
45 Correct 4 ms 7116 KB Output is correct
46 Correct 4 ms 7116 KB Output is correct
47 Correct 5 ms 7116 KB Output is correct
48 Correct 4 ms 7244 KB Output is correct
49 Correct 4 ms 7244 KB Output is correct
50 Correct 4 ms 7116 KB Output is correct
51 Correct 4 ms 7084 KB Output is correct
52 Correct 4 ms 6988 KB Output is correct
53 Correct 7 ms 8524 KB Output is correct
54 Correct 8 ms 9036 KB Output is correct
55 Correct 7 ms 7356 KB Output is correct
56 Correct 6 ms 7228 KB Output is correct
57 Correct 5 ms 7244 KB Output is correct
58 Correct 4 ms 6988 KB Output is correct
59 Correct 4 ms 7116 KB Output is correct
60 Correct 4 ms 7088 KB Output is correct
61 Correct 3 ms 6988 KB Output is correct
62 Correct 4 ms 6988 KB Output is correct
63 Correct 4 ms 6960 KB Output is correct
64 Correct 8 ms 8908 KB Output is correct
65 Correct 8 ms 9012 KB Output is correct
66 Correct 8 ms 7372 KB Output is correct
67 Correct 6 ms 7372 KB Output is correct
68 Correct 6 ms 7372 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 106444 KB Output is correct
2 Correct 330 ms 104756 KB Output is correct
3 Correct 173 ms 26688 KB Output is correct
4 Correct 342 ms 110376 KB Output is correct
5 Correct 140 ms 26688 KB Output is correct
6 Correct 140 ms 26160 KB Output is correct
7 Correct 241 ms 74684 KB Output is correct
8 Correct 119 ms 25280 KB Output is correct
9 Correct 344 ms 86140 KB Output is correct
10 Correct 334 ms 90060 KB Output is correct
11 Correct 168 ms 27544 KB Output is correct
12 Correct 123 ms 26696 KB Output is correct
13 Correct 3 ms 6860 KB Output is correct
14 Correct 182 ms 150004 KB Output is correct
15 Correct 189 ms 165628 KB Output is correct
16 Correct 7 ms 8908 KB Output is correct
17 Correct 8 ms 9036 KB Output is correct
18 Correct 6 ms 7352 KB Output is correct
19 Correct 6 ms 7352 KB Output is correct
20 Correct 6 ms 7364 KB Output is correct
21 Correct 106 ms 24900 KB Output is correct

Subtask #6
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 106444 KB Output is correct
2 Correct 330 ms 104756 KB Output is correct
3 Correct 173 ms 26688 KB Output is correct
4 Correct 342 ms 110376 KB Output is correct
5 Correct 140 ms 26688 KB Output is correct
6 Correct 140 ms 26160 KB Output is correct
7 Correct 241 ms 74684 KB Output is correct
8 Correct 119 ms 25280 KB Output is correct
9 Correct 344 ms 86140 KB Output is correct
10 Correct 334 ms 90060 KB Output is correct
11 Correct 168 ms 27544 KB Output is correct
12 Correct 123 ms 26696 KB Output is correct
13 Correct 3 ms 6860 KB Output is correct
14 Correct 182 ms 150004 KB Output is correct
15 Correct 189 ms 165628 KB Output is correct
16 Correct 7 ms 8908 KB Output is correct
17 Correct 8 ms 9036 KB Output is correct
18 Correct 6 ms 7352 KB Output is correct
19 Correct 6 ms 7352 KB Output is correct
20 Correct 6 ms 7364 KB Output is correct
21 Correct 106 ms 24900 KB Output is correct
22 Correct 4 ms 6860 KB Output is correct
23 Correct 3 ms 6860 KB Output is correct
24 Correct 4 ms 6860 KB Output is correct
25 Correct 295 ms 99168 KB Output is correct
26 Correct 280 ms 90712 KB Output is correct
27 Correct 359 ms 114952 KB Output is correct
28 Correct 177 ms 27524 KB Output is correct
29 Correct 137 ms 25848 KB Output is correct
30 Correct 140 ms 26076 KB Output is correct
31 Correct 130 ms 26612 KB Output is correct
32 Correct 289 ms 86952 KB Output is correct
33 Correct 118 ms 25640 KB Output is correct
34 Correct 249 ms 76668 KB Output is correct
35 Correct 362 ms 96300 KB Output is correct
36 Correct 188 ms 27768 KB Output is correct
37 Correct 130 ms 26812 KB Output is correct
38 Correct 119 ms 102336 KB Output is correct
39 Correct 208 ms 165708 KB Output is correct
40 Correct 7 ms 8512 KB Output is correct
41 Correct 8 ms 9016 KB Output is correct
42 Correct 6 ms 7372 KB Output is correct
43 Correct 5 ms 7244 KB Output is correct
44 Correct 5 ms 7244 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 7080 KB Output is correct
48 Correct 4 ms 6988 KB Output is correct
49 Correct 4 ms 6988 KB Output is correct
50 Correct 71 ms 19064 KB Output is correct
51 Correct 125 ms 26676 KB Output is correct
52 Correct 345 ms 107016 KB Output is correct
53 Correct 340 ms 105348 KB Output is correct
54 Correct 180 ms 27452 KB Output is correct
55 Correct 348 ms 110972 KB Output is correct
56 Correct 144 ms 27444 KB Output is correct
57 Correct 143 ms 26900 KB Output is correct
58 Correct 253 ms 74756 KB Output is correct
59 Correct 109 ms 25296 KB Output is correct
60 Correct 347 ms 86244 KB Output is correct
61 Correct 309 ms 89908 KB Output is correct
62 Correct 171 ms 27456 KB Output is correct
63 Correct 126 ms 26732 KB Output is correct
64 Correct 4 ms 6860 KB Output is correct
65 Correct 178 ms 149984 KB Output is correct
66 Correct 191 ms 165572 KB Output is correct
67 Correct 8 ms 8908 KB Output is correct
68 Correct 7 ms 9036 KB Output is correct
69 Correct 6 ms 7372 KB Output is correct
70 Correct 6 ms 7372 KB Output is correct
71 Correct 6 ms 7372 KB Output is correct
72 Correct 104 ms 24820 KB Output is correct

Subtask #7
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Correct 8 ms 8908 KB Output is correct
3 Correct 10 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 3 ms 6988 KB Output is correct
11 Correct 4 ms 6988 KB Output is correct
12 Correct 70 ms 18504 KB Output is correct
13 Correct 120 ms 26784 KB Output is correct
14 Correct 242 ms 77208 KB Output is correct
15 Correct 279 ms 88652 KB Output is correct
16 Correct 267 ms 87100 KB Output is correct
17 Correct 125 ms 26788 KB Output is correct
18 Correct 3 ms 6860 KB Output is correct
19 Correct 105 ms 24872 KB Output is correct
20 Correct 4 ms 6860 KB Output is correct
21 Correct 176 ms 137896 KB Output is correct
22 Correct 197 ms 154576 KB Output is correct
23 Correct 235 ms 164648 KB Output is correct
24 Correct 187 ms 160300 KB Output is correct
25 Correct 7 ms 9676 KB Output is correct
26 Correct 10 ms 10020 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 121 ms 101608 KB Output is correct
32 Correct 190 ms 165048 KB Output is correct
33 Correct 4 ms 6844 KB Output is correct
34 Correct 174 ms 149592 KB Output is correct
35 Correct 194 ms 165036 KB Output is correct
36 Correct 4 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 5 ms 7116 KB Output is correct
40 Correct 4 ms 7244 KB Output is correct
41 Correct 4 ms 6980 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 7216 KB Output is correct
45 Correct 5 ms 7236 KB Output is correct
46 Correct 6 ms 7244 KB Output is correct
47 Correct 4 ms 7244 KB Output is correct
48 Correct 5 ms 7116 KB Output is correct
49 Correct 5 ms 7116 KB Output is correct
50 Correct 4 ms 6988 KB Output is correct
51 Correct 4 ms 6988 KB Output is correct
52 Correct 4 ms 7080 KB Output is correct
53 Correct 4 ms 6988 KB Output is correct
54 Correct 4 ms 6960 KB Output is correct
55 Correct 4 ms 6956 KB Output is correct
56 Correct 3 ms 6860 KB Output is correct
57 Correct 4 ms 6860 KB Output is correct
58 Correct 7 ms 8760 KB Output is correct
59 Correct 10 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 12 ms 9276 KB Output is correct
63 Correct 7 ms 7488 KB Output is correct
64 Correct 9 ms 9668 KB Output is correct
65 Correct 10 ms 9272 KB Output is correct
66 Correct 7 ms 7372 KB Output is correct
67 Correct 6 ms 7372 KB Output is correct
68 Correct 7 ms 9676 KB Output is correct
69 Correct 8 ms 10048 KB Output is correct
70 Correct 8 ms 9648 KB Output is correct
71 Correct 7 ms 8908 KB Output is correct
72 Correct 8 ms 9088 KB Output is correct
73 Correct 5 ms 7372 KB Output is correct
74 Correct 4 ms 6860 KB Output is correct
75 Correct 3 ms 6860 KB Output is correct
76 Correct 4 ms 7116 KB Output is correct
77 Correct 4 ms 7212 KB Output is correct
78 Correct 4 ms 6988 KB Output is correct
79 Correct 5 ms 7188 KB Output is correct
80 Correct 4 ms 7116 KB Output is correct
81 Correct 4 ms 7116 KB Output is correct
82 Correct 5 ms 7116 KB Output is correct
83 Correct 4 ms 7244 KB Output is correct
84 Correct 4 ms 7244 KB Output is correct
85 Correct 4 ms 7116 KB Output is correct
86 Correct 4 ms 7084 KB Output is correct
87 Correct 4 ms 6988 KB Output is correct
88 Correct 7 ms 8524 KB Output is correct
89 Correct 8 ms 9036 KB Output is correct
90 Correct 7 ms 7356 KB Output is correct
91 Correct 6 ms 7228 KB Output is correct
92 Correct 5 ms 7244 KB Output is correct
93 Correct 4 ms 6988 KB Output is correct
94 Correct 4 ms 7116 KB Output is correct
95 Correct 4 ms 7088 KB Output is correct
96 Correct 3 ms 6988 KB Output is correct
97 Correct 4 ms 6988 KB Output is correct
98 Correct 4 ms 6960 KB Output is correct
99 Correct 8 ms 8908 KB Output is correct
100 Correct 8 ms 9012 KB Output is correct
101 Correct 8 ms 7372 KB Output is correct
102 Correct 6 ms 7372 KB Output is correct
103 Correct 6 ms 7372 KB Output is correct
104 Correct 328 ms 106444 KB Output is correct
105 Correct 330 ms 104756 KB Output is correct
106 Correct 173 ms 26688 KB Output is correct
107 Correct 342 ms 110376 KB Output is correct
108 Correct 140 ms 26688 KB Output is correct
109 Correct 140 ms 26160 KB Output is correct
110 Correct 241 ms 74684 KB Output is correct
111 Correct 119 ms 25280 KB Output is correct
112 Correct 344 ms 86140 KB Output is correct
113 Correct 334 ms 90060 KB Output is correct
114 Correct 168 ms 27544 KB Output is correct
115 Correct 123 ms 26696 KB Output is correct
116 Correct 3 ms 6860 KB Output is correct
117 Correct 182 ms 150004 KB Output is correct
118 Correct 189 ms 165628 KB Output is correct
119 Correct 7 ms 8908 KB Output is correct
120 Correct 8 ms 9036 KB Output is correct
121 Correct 6 ms 7352 KB Output is correct
122 Correct 6 ms 7352 KB Output is correct
123 Correct 6 ms 7364 KB Output is correct
124 Correct 106 ms 24900 KB Output is correct
125 Correct 4 ms 6860 KB Output is correct
126 Correct 3 ms 6860 KB Output is correct
127 Correct 4 ms 6860 KB Output is correct
128 Correct 295 ms 99168 KB Output is correct
129 Correct 280 ms 90712 KB Output is correct
130 Correct 359 ms 114952 KB Output is correct
131 Correct 177 ms 27524 KB Output is correct
132 Correct 137 ms 25848 KB Output is correct
133 Correct 140 ms 26076 KB Output is correct
134 Correct 130 ms 26612 KB Output is correct
135 Correct 289 ms 86952 KB Output is correct
136 Correct 118 ms 25640 KB Output is correct
137 Correct 249 ms 76668 KB Output is correct
138 Correct 362 ms 96300 KB Output is correct
139 Correct 188 ms 27768 KB Output is correct
140 Correct 130 ms 26812 KB Output is correct
141 Correct 119 ms 102336 KB Output is correct
142 Correct 208 ms 165708 KB Output is correct
143 Correct 7 ms 8512 KB Output is correct
144 Correct 8 ms 9016 KB Output is correct
145 Correct 6 ms 7372 KB Output is correct
146 Correct 5 ms 7244 KB Output is correct
147 Correct 5 ms 7244 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 7080 KB Output is correct
151 Correct 4 ms 6988 KB Output is correct
152 Correct 4 ms 6988 KB Output is correct
153 Correct 71 ms 19064 KB Output is correct
154 Correct 125 ms 26676 KB Output is correct
155 Correct 345 ms 107016 KB Output is correct
156 Correct 340 ms 105348 KB Output is correct
157 Correct 180 ms 27452 KB Output is correct
158 Correct 348 ms 110972 KB Output is correct
159 Correct 144 ms 27444 KB Output is correct
160 Correct 143 ms 26900 KB Output is correct
161 Correct 253 ms 74756 KB Output is correct
162 Correct 109 ms 25296 KB Output is correct
163 Correct 347 ms 86244 KB Output is correct
164 Correct 309 ms 89908 KB Output is correct
165 Correct 171 ms 27456 KB Output is correct
166 Correct 126 ms 26732 KB Output is correct
167 Correct 4 ms 6860 KB Output is correct
168 Correct 178 ms 149984 KB Output is correct
169 Correct 191 ms 165572 KB Output is correct
170 Correct 8 ms 8908 KB Output is correct
171 Correct 7 ms 9036 KB Output is correct
172 Correct 6 ms 7372 KB Output is correct
173 Correct 6 ms 7372 KB Output is correct
174 Correct 6 ms 7372 KB Output is correct
175 Correct 104 ms 24820 KB Output is correct
176 Correct 3 ms 6956 KB Output is correct
177 Correct 422 ms 156528 KB Output is correct
178 Correct 299 ms 125124 KB Output is correct
179 Correct 170 ms 27328 KB Output is correct
180 Correct 335 ms 121484 KB Output is correct
181 Correct 148 ms 27200 KB Output is correct
182 Correct 150 ms 27300 KB Output is correct
183 Correct 252 ms 75100 KB Output is correct
184 Correct 321 ms 104628 KB Output is correct
185 Correct 317 ms 98384 KB Output is correct
186 Correct 296 ms 92316 KB Output is correct
187 Correct 260 ms 84124 KB Output is correct
188 Correct 330 ms 106960 KB Output is correct
189 Correct 300 ms 88096 KB Output is correct
190 Correct 416 ms 114492 KB Output is correct
191 Correct 171 ms 27260 KB Output is correct
192 Correct 285 ms 83524 KB Output is correct
193 Correct 313 ms 99120 KB Output is correct
194 Correct 169 ms 27300 KB Output is correct
195 Correct 174 ms 138284 KB Output is correct
196 Correct 197 ms 154972 KB Output is correct
197 Correct 208 ms 164932 KB Output is correct
198 Correct 184 ms 160564 KB Output is correct
199 Correct 7 ms 8780 KB Output is correct
200 Correct 9 ms 9932 KB Output is correct
201 Correct 7 ms 8780 KB Output is correct
202 Correct 7 ms 8268 KB Output is correct
203 Correct 9 ms 9268 KB Output is correct
204 Correct 7 ms 7372 KB Output is correct
205 Correct 8 ms 9704 KB Output is correct
206 Correct 9 ms 9352 KB Output is correct
207 Correct 7 ms 7372 KB Output is correct
208 Correct 6 ms 7356 KB Output is correct
209 Correct 7 ms 9676 KB Output is correct
210 Correct 8 ms 10060 KB Output is correct
211 Correct 7 ms 9676 KB Output is correct
212 Correct 7 ms 8908 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 6860 KB Output is correct
216 Correct 4 ms 6860 KB Output is correct
217 Correct 4 ms 7076 KB Output is correct
218 Correct 5 ms 7172 KB Output is correct
219 Correct 5 ms 6988 KB Output is correct
220 Correct 5 ms 7116 KB Output is correct
221 Correct 5 ms 7116 KB Output is correct
222 Correct 4 ms 7116 KB Output is correct
223 Correct 4 ms 7116 KB Output is correct
224 Correct 4 ms 7244 KB Output is correct
225 Correct 4 ms 7244 KB Output is correct
226 Correct 4 ms 7116 KB Output is correct
227 Correct 4 ms 7092 KB Output is correct
228 Correct 4 ms 6988 KB Output is correct
229 Correct 297 ms 98824 KB Output is correct
230 Correct 270 ms 90376 KB Output is correct
231 Correct 353 ms 114624 KB Output is correct
232 Correct 178 ms 27076 KB Output is correct
233 Correct 141 ms 25428 KB Output is correct
234 Correct 131 ms 25644 KB Output is correct
235 Correct 127 ms 26196 KB Output is correct
236 Correct 301 ms 86732 KB Output is correct
237 Correct 114 ms 25276 KB Output is correct
238 Correct 246 ms 76276 KB Output is correct
239 Correct 378 ms 95984 KB Output is correct
240 Correct 202 ms 27200 KB Output is correct
241 Correct 125 ms 26384 KB Output is correct
242 Correct 119 ms 101924 KB Output is correct
243 Correct 194 ms 165144 KB Output is correct
244 Correct 6 ms 8524 KB Output is correct
245 Correct 9 ms 9036 KB Output is correct
246 Correct 6 ms 7372 KB Output is correct
247 Correct 5 ms 7244 KB Output is correct
248 Correct 5 ms 7244 KB Output is correct
249 Correct 4 ms 6988 KB Output is correct
250 Correct 4 ms 7088 KB Output is correct
251 Correct 4 ms 6988 KB Output is correct
252 Correct 4 ms 6988 KB Output is correct
253 Correct 4 ms 6988 KB Output is correct
254 Correct 72 ms 18608 KB Output is correct
255 Correct 122 ms 26176 KB Output is correct
256 Correct 234 ms 76608 KB Output is correct
257 Correct 278 ms 88364 KB Output is correct
258 Correct 263 ms 86588 KB Output is correct
259 Correct 125 ms 26176 KB Output is correct
260 Correct 341 ms 106540 KB Output is correct
261 Correct 325 ms 104820 KB Output is correct
262 Correct 169 ms 26820 KB Output is correct
263 Correct 355 ms 110452 KB Output is correct
264 Correct 144 ms 26808 KB Output is correct
265 Correct 142 ms 26308 KB Output is correct
266 Correct 255 ms 74240 KB Output is correct
267 Correct 107 ms 24708 KB Output is correct
268 Correct 329 ms 85784 KB Output is correct
269 Correct 305 ms 89500 KB Output is correct
270 Correct 164 ms 26920 KB Output is correct
271 Correct 128 ms 26176 KB Output is correct
272 Correct 4 ms 6860 KB Output is correct
273 Correct 176 ms 149308 KB Output is correct
274 Correct 190 ms 165060 KB Output is correct
275 Correct 7 ms 8908 KB Output is correct
276 Correct 8 ms 8908 KB Output is correct
277 Correct 6 ms 7372 KB Output is correct
278 Correct 8 ms 7232 KB Output is correct
279 Correct 6 ms 7372 KB Output is correct
280 Correct 112 ms 24340 KB Output is correct