oj.uz

Submission #497082

# Submission time Handle Problem Language Result Execution time Memory
497082 2021-12-22T10:42:22 Z Jarif_Rahman Unique Cities (JOI19_ho_t5) C++17
36 / 100
 1265 ms 274436 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int k = 19;
const int inf = 1e8;

struct persistent_segtree{
    struct node{
        int sm;
        node *l, *r;
        node(){
            sm = 0;
        }
        node(int x){
            sm = x;
        }
        node(node* _l, node* _r){
            l = _l, r = _r;
            sm = l->sm+r->sm;
        }
    };
    int k;
    persistent_segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
    }
    void init(node* nd, int kk){
        if(kk < 2) return;
        nd->l = new node();
        nd->r = new node();
        kk/=2;
        init(nd->l, kk);
        init(nd->r, kk);
    }
    node* init(){
        node* root = new node();
        init(root, k);
        return root;
    }
    node* upd(int in, node* nd, int a, int b, int x){
        if(a == b) return new node(x);
        int md = (a+b)/2;
        if(in <= md) return new node(upd(in, nd->l, a, md, x), nd->r);
        else return new node(nd->l, upd(in, nd->r, md+1, b, x));
    }
    node* upd(node* nd, int in, int x){
        return upd(in, nd, 0, k/2-1, x);
    }
    int sum(int l, int r, node* nd, int a, int b){
        if(a > r || b < l) return 0;
        if(a >= l && b <= r) return nd->sm;
        int md = (a+b)/2;
        return sum(l, r, nd->l, a, md)+sum(l, r, nd->r, md+1, b);
    }
    int sum(node* nd, int l, int r){
        return sum(l, r, nd, 0, k/2-1);
    }
};

int n, m;
vector<int> C;
vector<vector<int>> v;
vector<vector<pair<int, int>>> anc;
vector<int> cnt;
vector<persistent_segtree::node*> pss;
vector<int> mxh;
vector<int> ans;

persistent_segtree ps(0);

pair<int, int> next(int nd, int h){
    if(h == 0) return {nd, 0};
    for(int i = k-1; i >= 0; i--){
        if(anc[nd][i].sc <= h){
            h-=anc[nd][i].sc;
            auto nxt = next(anc[nd][i].f, h);
            nxt.sc+=anc[nd][i].sc;
            return nxt;
        }
    }
    return {anc[nd][0].f, anc[nd][0].sc};
}

void dfs0(int nd, int ss){
    for(int x: v[nd]) if(x != ss) dfs0(x, nd);
    int mx = 0, smx = 0, in = n;
    for(int x: v[nd]) if(x != ss){
        if(mxh[x] > mx) smx = mx, mx = mxh[x], in = x;
        else if(mxh[x] > smx) smx = mxh[x];
    }
    mxh[nd] = mxh[in]+1;
    auto nxt = next(in, smx);
    nxt.sc++;
    nxt.sc = min(nxt.sc, inf);
    anc[nd][0] = nxt;
    for(int i = 1; i < k; i++){
        anc[nd][i].f = anc[anc[nd][i-1].f][i-1].f;
        anc[nd][i].sc = anc[nd][i-1].sc + anc[anc[nd][i-1].f][i-1].sc;
        anc[nd][i].sc = min(anc[nd][i].sc, inf);
    }
    cnt[nd] = cnt[nxt.f];
    pss[nd] = pss[nxt.f];
    if(ps.sum(pss[nd], C[nd], C[nd]) == 0){
        cnt[nd]++;
        pss[nd] = ps.upd(pss[nd], C[nd], 1);
    }
}

void dfs1(int nd, int ss){
    vector<pair<int, int>> sth;
    for(int x: v[nd]) sth.pb({mxh[x], x});
    sort(sth.rbegin(), sth.rend());
    while(sth.size() < 3) sth.pb({0, n});

    auto nxt = next(sth[0].sc, sth[1].f);
    ans[nd] = cnt[nxt.f];

    auto old_anc = anc[nd];
    int old_cnt = cnt[nd], old_mxh = mxh[nd];
    auto old_pss = pss[nd];
    for(int x: v[nd]) if(x != ss){
        pair<int, int> nxt;
        if(x == sth[0].sc) nxt = next(sth[1].sc, sth[2].f), mxh[nd] = mxh[sth[1].sc]+1;
        else if(x == sth[1].sc) nxt = next(sth[0].sc, sth[2].f), mxh[nd] = mxh[sth[0].sc]+1;
        else nxt = next(sth[0].sc, sth[1].f), mxh[nd] = mxh[sth[0].sc]+1;

        nxt.sc++;
        nxt.sc = min(nxt.sc, inf);

        anc[nd][0] = nxt;
        for(int i = 1; i < k; i++){
            anc[nd][i].f = anc[anc[nd][i-1].f][i-1].f;
            anc[nd][i].sc = anc[nd][i-1].sc + anc[anc[nd][i-1].f][i-1].sc;
            anc[nd][i].sc = min(anc[nd][i].sc, inf);
        }
        cnt[nd] = cnt[nxt.f];
        pss[nd] = pss[nxt.f];
        if(ps.sum(pss[nd], C[nd], C[nd]) == 0){
            cnt[nd]++;
            pss[nd] = ps.upd(pss[nd], C[nd], 1);
        }
        dfs1(x, nd);
    }
    anc[nd] = old_anc;
    cnt[nd] = old_cnt;
    mxh[nd] = old_mxh;
    pss[nd] = old_pss;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    C.resize(n);
    v.resize(n);
    anc.resize(n+1, vector<pair<int, int>>(k, {n, inf}));
    cnt.resize(n+1, 0);
    mxh.resize(n+1, 1);
    mxh[n] = 0;
    ans.resize(n);

    for(int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--, b--;
        v[a].pb(b);
        v[b].pb(a);
    }

    for(int &x: C) cin >> x, x--;

    ps = persistent_segtree(m);
    auto init = ps.init();
    pss.resize(n+1, init);

    dfs0(0, -1);
    dfs1(0, -1);

    for(int x: ans) cout << x << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 2104 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 5 ms 1740 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct
6 Correct 5 ms 1196 KB Output is correct
7 Correct 3 ms 1096 KB Output is correct
8 Correct 3 ms 1228 KB Output is correct
9 Correct 3 ms 1356 KB Output is correct
10 Correct 3 ms 1092 KB Output is correct
11 Correct 3 ms 1328 KB Output is correct
12 Correct 3 ms 1348 KB Output is correct
13 Correct 3 ms 1196 KB Output is correct
14 Correct 3 ms 1096 KB Output is correct
15 Correct 3 ms 1200 KB Output is correct
16 Correct 3 ms 1344 KB Output is correct
17 Correct 3 ms 1452 KB Output is correct
18 Correct 3 ms 1100 KB Output is correct
19 Correct 5 ms 2380 KB Output is correct
20 Correct 5 ms 2588 KB Output is correct
21 Correct 5 ms 2508 KB Output is correct
22 Correct 4 ms 1980 KB Output is correct
23 Correct 5 ms 2628 KB Output is correct
24 Correct 5 ms 2380 KB Output is correct
25 Correct 5 ms 2380 KB Output is correct
26 Correct 4 ms 2116 KB Output is correct
27 Correct 7 ms 2636 KB Output is correct
28 Correct 7 ms 2612 KB Output is correct
29 Correct 6 ms 2628 KB Output is correct
30 Correct 4 ms 2124 KB Output is correct
31 Correct 4 ms 1724 KB Output is correct
32 Correct 6 ms 2488 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 33488 KB Output is correct
2 Correct 505 ms 69220 KB Output is correct
3 Correct 57 ms 12748 KB Output is correct
4 Correct 377 ms 56308 KB Output is correct
5 Correct 1020 ms 96708 KB Output is correct
6 Correct 759 ms 91748 KB Output is correct
7 Correct 430 ms 56760 KB Output is correct
8 Correct 432 ms 62308 KB Output is correct
9 Correct 432 ms 61556 KB Output is correct
10 Correct 437 ms 61516 KB Output is correct
11 Correct 373 ms 66380 KB Output is correct
12 Correct 818 ms 107328 KB Output is correct
13 Correct 643 ms 78356 KB Output is correct
14 Correct 673 ms 84080 KB Output is correct
15 Correct 337 ms 67332 KB Output is correct
16 Correct 738 ms 84736 KB Output is correct
17 Correct 755 ms 82924 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 262748 KB Output is correct
2 Runtime error 1265 ms 274436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 2104 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 5 ms 1740 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct
6 Correct 5 ms 1196 KB Output is correct
7 Correct 3 ms 1096 KB Output is correct
8 Correct 3 ms 1228 KB Output is correct
9 Correct 3 ms 1356 KB Output is correct
10 Correct 3 ms 1092 KB Output is correct
11 Correct 3 ms 1328 KB Output is correct
12 Correct 3 ms 1348 KB Output is correct
13 Correct 3 ms 1196 KB Output is correct
14 Correct 3 ms 1096 KB Output is correct
15 Correct 3 ms 1200 KB Output is correct
16 Correct 3 ms 1344 KB Output is correct
17 Correct 3 ms 1452 KB Output is correct
18 Correct 3 ms 1100 KB Output is correct
19 Correct 5 ms 2380 KB Output is correct
20 Correct 5 ms 2588 KB Output is correct
21 Correct 5 ms 2508 KB Output is correct
22 Correct 4 ms 1980 KB Output is correct
23 Correct 5 ms 2628 KB Output is correct
24 Correct 5 ms 2380 KB Output is correct
25 Correct 5 ms 2380 KB Output is correct
26 Correct 4 ms 2116 KB Output is correct
27 Correct 7 ms 2636 KB Output is correct
28 Correct 7 ms 2612 KB Output is correct
29 Correct 6 ms 2628 KB Output is correct
30 Correct 4 ms 2124 KB Output is correct
31 Correct 4 ms 1724 KB Output is correct
32 Correct 6 ms 2488 KB Output is correct
33 Correct 213 ms 33488 KB Output is correct
34 Correct 505 ms 69220 KB Output is correct
35 Correct 57 ms 12748 KB Output is correct
36 Correct 377 ms 56308 KB Output is correct
37 Correct 1020 ms 96708 KB Output is correct
38 Correct 759 ms 91748 KB Output is correct
39 Correct 430 ms 56760 KB Output is correct
40 Correct 432 ms 62308 KB Output is correct
41 Correct 432 ms 61556 KB Output is correct
42 Correct 437 ms 61516 KB Output is correct
43 Correct 373 ms 66380 KB Output is correct
44 Correct 818 ms 107328 KB Output is correct
45 Correct 643 ms 78356 KB Output is correct
46 Correct 673 ms 84080 KB Output is correct
47 Correct 337 ms 67332 KB Output is correct
48 Correct 738 ms 84736 KB Output is correct
49 Correct 755 ms 82924 KB Output is correct
50 Correct 797 ms 262748 KB Output is correct
51 Runtime error 1265 ms 274436 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -