oj.uz

Submission #805488

# Submission time Handle Problem Language Result Execution time Memory
805488 2023-08-03T17:03:58 Z Hakiers Synchronization (JOI13_synchronization) C++17
0 / 100
 1091 ms 62368 KB 
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int MAXN = 1e5 + 7;
const int BASE = 1 << 18;
vector<pair<int, int>> G[MAXN];
vector<tuple<int ,int, int, int, pair<int, int>>> accensor[MAXN];
vector<pair<int, int>> edges;
int depth[MAXN];
bool off[MAXN];
int sajz[MAXN];
int parent[MAXN];
int pre[MAXN];
int post[MAXN];
int TREE[BASE << 1];
int vertex[MAXN];
int howaddedge[MAXN];
bool active[MAXN];
int tajm;
int n, q, m;


void dfs_pre(int v, int p, int d = 0){
    depth[v] = d;
    for(auto [u, id] : G[v]){
        if(id == p) continue;
        pre[id] = ++tajm;
        dfs_pre(u, id, d+1);
    }
    
    post[p] = ++tajm;
}

void dfs(int v, int p){

    sajz[v] = 1;
    parent[v] = p;
    for(auto [u, id] : G[v]){
        if(off[u] || u == p) continue;
        dfs(u, v);
        sajz[v] += sajz[u];
    }
}

void mark(int v, int p, int centro, int uout, int d, pair<int, int> lca){

    accensor[v].push_back({centro, d, p, uout, lca});

    for(auto [u, id]: G[v]){
        if(off[u] || id == p) continue;
        if(depth[u] < depth[v]) mark(u, id, centro, uout, d+1, make_pair(u, u));
        else if(lca.first == v) mark(u, id, centro, uout, d+1, make_pair(p, id));
        else mark(u, id, centro, uout, d+1, lca);
    }
}

int find_centroid(int v, int tree_size){

    for(auto [u, id] : G[v]){
        if(off[u]) continue;
        if(u == parent[v]){
            if(tree_size - sajz[v] > tree_size/2) return find_centroid(u, tree_size);
        }
        else if(sajz[u] > tree_size/2) return find_centroid(u, tree_size);
    }
    return v;
}

void centroid_decomposition(int V, int tree_size){

    if(tree_size == 1) return;

    dfs(V, 0);
    int centroid = find_centroid(V, tree_size);
    off[centroid] = 1;


    for(auto [u, id] : G[centroid]){
        if(off[u]) continue;

        if(depth[u] < depth[centroid]) mark(u, id, centroid, id, 1, make_pair(u, u));
        else mark(u, id, centroid, id, 1, make_pair(centroid, centroid));
    }


    for(auto [u, id] : G[centroid]){
        if(off[u]) continue;
        int new_size = (sajz[u] < sajz[centroid] ? sajz[u]: tree_size - sajz[centroid]);
        centroid_decomposition(u, new_size);
    }
}

void update(int v, int val){

    v += BASE;
    TREE[v] = val;

    v/=2;

    while(v > 0){
        int l = 2*v, r = 2*v + 1;
        TREE[v] = TREE[l] + TREE[r];
        v/=2;
    }
}

int query(int a, int b){
    if(b < a) swap(a, b);
    a += BASE - 1;
    b += BASE + 1;

    int res = 0;

    while(a/2 != b/2){

        if(a % 2 == 0) res += TREE[a+1];
        if(b % 2 == 1) res += TREE[b-1];

        a/=2; b/=2;
    }

    return res;
}

int ask(int v){
    int sum = vertex[v];
    for(auto [centroid, d, p, uout, lca] : accensor[v]){
        if(lca.first != lca.second){
            int tmp = query(pre[lca.first], pre[uout]) + query(pre[lca.second], pre[p]);
            if(d == tmp) sum = max(sum, vertex[centroid]);
        }
        else{
            int tmp = query(pre[p], pre[uout]);
            if(d == tmp) sum = max(sum, vertex[centroid]);
        }

    }

    return sum;
}

void update_centroid(int v, int val){
    vertex[v] = val;
    for(auto [centroid, d, p, uout, lca] : accensor[v]){
        if(lca.first != lca.second){
            int tmp = query(pre[lca.first], pre[uout]) + query(pre[lca.second], pre[p]);
            if(d == tmp) vertex[centroid] = max(vertex[centroid], val);
        }
        else{
            int tmp = query(pre[p], pre[uout]);
            if(d == tmp) vertex[centroid] = max(vertex[centroid], val);
        }

    }

}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q >> m;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b, i});
        G[b].push_back({a, i});
        edges.push_back({a, b});
        vertex[a] = vertex[b] = 1;
    }

    dfs_pre(1, 0);

    centroid_decomposition(1, n);

    for(int i = 1; i <= q; i++){

        int x;
        cin >> x;
        if(!active[x]){
            auto [a, b] = edges[x-1];
            vertex[a] = ask(a);
            vertex[b] = ask(b);
            int tmp = howaddedge[x];
            howaddedge[x] = vertex[a] + vertex[b] - howaddedge[x];
            update(pre[x], 1);
            update(post[x], -1);

            if(tmp < howaddedge[x]){
                update_centroid(a, howaddedge[x]);
                update_centroid(b, howaddedge[x]);
            }

        }
        else{
            auto [a, b] = edges[x-1];
            vertex[a] = ask(a);
            vertex[b] = ask(b);
            howaddedge[x] = vertex[a];
            
            update(pre[x], 0);
            update(post[x], 0);
        }
        active[x] ^= 1;
    }

    for(int i = 1; i <= m; i++){
        int x;
        cin >> x;
        cout << vertex[x] << endl;
    }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 345 ms 41788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 2 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1091 ms 62368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Incorrect 2 ms 5032 KB Output isn't correct
4 Halted 0 ms 0 KB -