oj.uz

Submission #497105

# Submission time Handle Problem Language Result Execution time Memory
497105 2021-12-22T12:05:20 Z Jarif_Rahman Unique Cities (JOI19_ho_t5) C++17
36 / 100
 1131 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 = 15;
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 0 ms 204 KB Output is correct
2 Correct 4 ms 2116 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 4 ms 1732 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 4 ms 1216 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 3 ms 960 KB Output is correct
11 Correct 3 ms 1216 KB Output is correct
12 Correct 3 ms 1228 KB Output is correct
13 Correct 3 ms 1140 KB Output is correct
14 Correct 3 ms 1000 KB Output is correct
15 Correct 5 ms 1200 KB Output is correct
16 Correct 3 ms 1216 KB Output is correct
17 Correct 3 ms 1348 KB Output is correct
18 Correct 4 ms 956 KB Output is correct
19 Correct 5 ms 2288 KB Output is correct
20 Correct 6 ms 2420 KB Output is correct
21 Correct 5 ms 2492 KB Output is correct
22 Correct 4 ms 1864 KB Output is correct
23 Correct 5 ms 2508 KB Output is correct
24 Correct 5 ms 2252 KB Output is correct
25 Correct 6 ms 2268 KB Output is correct
26 Correct 4 ms 2016 KB Output is correct
27 Correct 5 ms 2636 KB Output is correct
28 Correct 5 ms 2508 KB Output is correct
29 Correct 6 ms 2620 KB Output is correct
30 Correct 4 ms 2124 KB Output is correct
31 Correct 5 ms 1592 KB Output is correct
32 Correct 7 ms 2496 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 30944 KB Output is correct
2 Correct 430 ms 63944 KB Output is correct
3 Correct 49 ms 11580 KB Output is correct
4 Correct 417 ms 51700 KB Output is correct
5 Correct 918 ms 88668 KB Output is correct
6 Correct 663 ms 84128 KB Output is correct
7 Correct 392 ms 51972 KB Output is correct
8 Correct 432 ms 57148 KB Output is correct
9 Correct 425 ms 56544 KB Output is correct
10 Correct 418 ms 56416 KB Output is correct
11 Correct 362 ms 61632 KB Output is correct
12 Correct 702 ms 98884 KB Output is correct
13 Correct 618 ms 71988 KB Output is correct
14 Correct 666 ms 77172 KB Output is correct
15 Correct 339 ms 62464 KB Output is correct
16 Correct 686 ms 77964 KB Output is correct
17 Correct 659 ms 76576 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 259436 KB Output is correct
2 Runtime error 1131 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 0 ms 204 KB Output is correct
2 Correct 4 ms 2116 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 4 ms 1732 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 4 ms 1216 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 3 ms 960 KB Output is correct
11 Correct 3 ms 1216 KB Output is correct
12 Correct 3 ms 1228 KB Output is correct
13 Correct 3 ms 1140 KB Output is correct
14 Correct 3 ms 1000 KB Output is correct
15 Correct 5 ms 1200 KB Output is correct
16 Correct 3 ms 1216 KB Output is correct
17 Correct 3 ms 1348 KB Output is correct
18 Correct 4 ms 956 KB Output is correct
19 Correct 5 ms 2288 KB Output is correct
20 Correct 6 ms 2420 KB Output is correct
21 Correct 5 ms 2492 KB Output is correct
22 Correct 4 ms 1864 KB Output is correct
23 Correct 5 ms 2508 KB Output is correct
24 Correct 5 ms 2252 KB Output is correct
25 Correct 6 ms 2268 KB Output is correct
26 Correct 4 ms 2016 KB Output is correct
27 Correct 5 ms 2636 KB Output is correct
28 Correct 5 ms 2508 KB Output is correct
29 Correct 6 ms 2620 KB Output is correct
30 Correct 4 ms 2124 KB Output is correct
31 Correct 5 ms 1592 KB Output is correct
32 Correct 7 ms 2496 KB Output is correct
33 Correct 209 ms 30944 KB Output is correct
34 Correct 430 ms 63944 KB Output is correct
35 Correct 49 ms 11580 KB Output is correct
36 Correct 417 ms 51700 KB Output is correct
37 Correct 918 ms 88668 KB Output is correct
38 Correct 663 ms 84128 KB Output is correct
39 Correct 392 ms 51972 KB Output is correct
40 Correct 432 ms 57148 KB Output is correct
41 Correct 425 ms 56544 KB Output is correct
42 Correct 418 ms 56416 KB Output is correct
43 Correct 362 ms 61632 KB Output is correct
44 Correct 702 ms 98884 KB Output is correct
45 Correct 618 ms 71988 KB Output is correct
46 Correct 666 ms 77172 KB Output is correct
47 Correct 339 ms 62464 KB Output is correct
48 Correct 686 ms 77964 KB Output is correct
49 Correct 659 ms 76576 KB Output is correct
50 Correct 759 ms 259436 KB Output is correct
51 Runtime error 1131 ms 274436 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -