oj.uz

Submission #300191

# Submission time Handle Problem Language Result Execution time Memory
300191 2020-09-16T23:20:40 Z gevacrt Synchronization (JOI13_synchronization) C++17
100 / 100
 659 ms 29432 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

class SegTree{
    vi st; int l, r;

    void build(int node, int l, int r){
        if(l == r){
            st[node] = l;
            return;
        }
        int m = (l + r) / 2;
        build(node*2, l, m);
        build(node*2+1, m+1, r);
        st[node] = max(st[node*2], st[node*2+1]);
        return;
    }
    void Update(int node, int l, int r, int L, int R){
        if(r < L or R < l) return;
        if(L <= l and r <= R){
            st[node] = (st[node]==-1?l:-1);
            return;
        }

        int m = (l+r)>>1;
        Update(node*2, l, m, L, R);
        Update(node*2+1, m+1, r, L, R);
        st[node] = max(st[node*2], st[node*2+1]);
        return;
    }

    int Query(int node, int l, int r, int L, int R){
        if(r < L or R < l) return -1;
        if(L <= l and r <= R) return st[node];
        int m = (l+r)>>1;
        int v2 = Query(node*2+1, m+1, r, L, R);
        if(v2 == -1) return Query(node*2, l, m, L, R);
        return v2;
    }

    public:
        SegTree(int l, int r){
            int sz = (r-l+1);
            st = vi(4*sz);
            this->l = l, this->r = r;
            build(1, l, r);
        }

        void Update(int L, int R){
            Update(1, l, r, L, R);
            return;
        }

        int Query(int L, int R){
            return Query(1, l, r, L, R);
        }
};

class HLD{
    vi heavy, head, pos; // [next node, root of chain, index]
    vi parent, depth;
    int pos_timer = 0;
    SegTree ST;

    vi ppos, val, prev;

    int dfs(int u, const vvi &adj){
        int subtree_size = 1, max_size = 0;
        for(auto v : adj[u]){
            if(v == parent[u]) continue;
            parent[v] = u, depth[v] = depth[u]+1;
            int child_subtree_size = dfs(v, adj);
            subtree_size += child_subtree_size;
            if(max_size < child_subtree_size){
                max_size = child_subtree_size;
                heavy[u] = v;
            }
        }
        return subtree_size;
    }

    void decompose(int u, int h, const vvi &adj){
        head[u] = h; pos[u] = pos_timer++;
        ppos[pos[u]] = u;
        if(heavy[u] != -1)
            decompose(heavy[u], h, adj);
        for(auto v : adj[u]){
            if(v == parent[u] || v == heavy[u]) continue;
            decompose(v, v, adj);
        }
        return;
    }

    int find_root(int u){
        for(int a = u; ; a = parent[head[a]]){
            int qry = ST.Query(pos[head[a]], pos[a]);
            if(qry == -1) continue;
            int x = ppos[qry];
            return x;
        }
        // impossible case
        assert(false);
        return -1;
    }

    public:
        HLD(const vvi &adj) : ST(0, adj.size()-1){
            int N = adj.size(); // !!0 based indexing!!
            heavy = vi(N, -1), head = vi(N), pos = vi(N);
            parent = vi(N), depth = vi(N);
            ppos = vi(N), val = vi(N, 1), prev = vi(N);

            dfs(0, adj);
            decompose(0, 0, adj);
        }

        void Update(int u, int v){
            if(depth[u] > depth[v]) swap(u, v);

            if(ST.Query(pos[v], pos[v]) != -1){
                int par = find_root(u);
                val[par] += val[v]-prev[v];
            }else{
                int par = find_root(u);
                prev[v] = val[v] = val[par];
            }
            ST.Update(pos[v], pos[v]);
            return;
        }

        int Query(int u){
            return val[find_root(u)];
        }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q; cin >> N >> M >> Q;
    vii J(N); vvi adj(N);
    for(int x = 0; x < N-1; x++){
        int u, v; cin >> u >> v;
        u--, v--;
        J[x] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    HLD hvt(adj);

    while(M--){
        int i; cin >> i; i--;
        hvt.Update(J[i].first, J[i].second);
    }

    while(Q--){
        int u; cin >> u; u--;
        cout << hvt.Query(u) << endl;
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 21 ms 2304 KB Output is correct
8 Correct 20 ms 2304 KB Output is correct
9 Correct 20 ms 2304 KB Output is correct
10 Correct 370 ms 20052 KB Output is correct
11 Correct 380 ms 19832 KB Output is correct
12 Correct 312 ms 28664 KB Output is correct
13 Correct 290 ms 19564 KB Output is correct
14 Correct 295 ms 19192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 23924 KB Output is correct
2 Correct 138 ms 23668 KB Output is correct
3 Correct 109 ms 28024 KB Output is correct
4 Correct 112 ms 27896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 43 ms 3200 KB Output is correct
8 Correct 531 ms 29304 KB Output is correct
9 Correct 531 ms 29304 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 29328 KB Output is correct
2 Correct 350 ms 28896 KB Output is correct
3 Correct 359 ms 29176 KB Output is correct
4 Correct 377 ms 29048 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 46 ms 2304 KB Output is correct
7 Correct 659 ms 20728 KB Output is correct
8 Correct 558 ms 29432 KB Output is correct
9 Correct 496 ms 20844 KB Output is correct
10 Correct 629 ms 20472 KB Output is correct
11 Correct 398 ms 25076 KB Output is correct
12 Correct 397 ms 25204 KB Output is correct
13 Correct 352 ms 29176 KB Output is correct