Submission #590971

#	Time	Username	Problem	Language	Result	Execution time	Memory
590971		socpite	Synchronization (JOI13_synchronization)	C++14	0 / 100	159 ms	22744 KiB

synchronization

#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);
        else upd(mid+1, r, k, id);
        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[nw]=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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40