oj.uz

Submission #590979

# Submission time Handle Problem Language Result Execution time Memory
590979 2022-07-06T16:33:41 Z socpite Synchronization (JOI13_synchronization) C++14
100 / 100
 166 ms 25184 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int inf = 1e9;
const int mod = 998244353;
const int maxn = 2e5+5;

typedef long long ll;

int timedfs;

int n, m, q;

int A[maxn], sz[maxn], head[maxn], bc[maxn], pos[maxn], idx[maxn], pp[maxn], dep[maxn], R[maxn], col[maxn], diff[maxn], ans[maxn];
int st[4*maxn];

vector<int> tree[maxn];
pair<int, int> E[maxn];

void pre_dfs(int x, int p){
    sz[x]=1;
    int mx = 0;
    for(auto v: tree[x]){
        if(v==p)continue;
        dep[v]=dep[x]+1;
        pre_dfs(v, x);
        pp[v]=x;
        if(sz[v] > sz[mx])mx=v;
        sz[x]+=sz[v];
    }
    bc[mx]=1;
}

void hld(int x, int p){
    pos[x]=R[x]=++timedfs;
    idx[timedfs]=x;
    for(auto v: tree[x]){
        if(v==p)continue;
        if(bc[v]){
            head[v]=head[x];
            hld(v, x);
            R[x]=R[v];
        }
    }
    for(auto v: tree[x]){
        if(v==p)continue;
        if(!bc[v]){
            head[v]=v;
            hld(v, x);
            R[x]=R[v];
        }
    }
}

int Find(int l, int r, int ql, int qr, int id){
    if(qr < l || ql > r)return 0;
    else if(qr >= r && ql <= l){
        return st[id];
    }
    else{
        int mid = (l+r)>>1;
        return max(Find(l, mid, ql, qr, id<<1), Find(mid+1, r, ql, qr, id<<1|1));
    }
}

void upd(int l, int r, int k, int id){
    if(l==r){
        col[k]^=1;
        st[id]=(col[k]?0:l);
    }
    else{
        int mid = (l+r)>>1;
        if(k<=mid)upd(l, mid, k, id<<1);
        else upd(mid+1, r, k, id<<1|1);
        st[id]=max(st[id<<1], st[id<<1|1]);
    }
}

int gt(int x){
    int re = Find(1, n, pos[head[x]], pos[x], 1);
    if(re)return idx[re];
    else return gt(pp[head[x]]);
}

void build(int l, int r, int id){
    st[id]=r;
    if(l<r){
        int mid = (l+r)>>1;
        build(l, mid, id<<1);
        build(mid+1, r, id<<1|1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
        E[i] = {a, b};
    }
    for(int i = 1; i <= n; i++)diff[i]=ans[i]=1;
    pre_dfs(1, 0);
    head[1]=1;
    hld(1, 0);
    build(1, n, 1);
    for(int i = 1; i < n; i++)if(dep[E[i].f] > dep[E[i].s])swap(E[i].f, E[i].s);
    while(m--){
        int id;
        cin >> id;
        int nw = gt(E[id].f);
        if(col[pos[E[id].s]]){
            diff[E[id].s]=0;
            ans[E[id].s]=ans[nw];
        }
        else{
            diff[nw]+=diff[E[id].s];
            ans[nw]+=diff[E[id].s];
            diff[E[id].s]=0;
        }
        upd(1, n, pos[E[id].s], 1);
        //cout << col[pos[E[id].s]] << endl;
    }
    for(int i = 2; i <= n; i++){
        if(col[i])ans[idx[i]]=ans[pp[idx[i]]];
    }
    while(q--){
        int x;
        cin >> x;
        cout << ans[x] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5060 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 13 ms 6240 KB Output is correct
8 Correct 13 ms 6216 KB Output is correct
9 Correct 13 ms 6228 KB Output is correct
10 Correct 152 ms 16624 KB Output is correct
11 Correct 160 ms 16696 KB Output is correct
12 Correct 116 ms 24420 KB Output is correct
13 Correct 95 ms 16128 KB Output is correct
14 Correct 114 ms 16140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 18180 KB Output is correct
2 Correct 87 ms 20020 KB Output is correct
3 Correct 65 ms 23804 KB Output is correct
4 Correct 64 ms 23844 KB Output is correct

Subtask #3
10.0 / 10.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 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 13 ms 6996 KB Output is correct
8 Correct 142 ms 25180 KB Output is correct
9 Correct 138 ms 25184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 22256 KB Output is correct
2 Correct 79 ms 24880 KB Output is correct
3 Correct 80 ms 24944 KB Output is correct
4 Correct 91 ms 24984 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 16 ms 6284 KB Output is correct
7 Correct 166 ms 17484 KB Output is correct
8 Correct 141 ms 25184 KB Output is correct
9 Correct 111 ms 17284 KB Output is correct
10 Correct 140 ms 17484 KB Output is correct
11 Correct 97 ms 21388 KB Output is correct
12 Correct 117 ms 21520 KB Output is correct
13 Correct 80 ms 24932 KB Output is correct