Submission #300191

#	Time	Username	Problem	Language	Result	Execution time	Memory
300191		gevacrt	Synchronization (JOI13_synchronization)	C++17	100 / 100	659 ms	29432 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40