Submission #474035

#	Time	Username	Problem	Language	Result	Execution time	Memory
474035		nicolaalexandra	Synchronization (JOI13_synchronization)	C++14	100 / 100	838 ms	25892 KiB

synchronization

#include <bits/stdc++.h>
#define DIM 200010
using namespace std;

vector <int> L[DIM];
pair <int,int> poz[DIM],mch[DIM];
int E[DIM],level[DIM],fth[DIM],stramos[22][DIM],aib[DIM],v[DIM],c[DIM],stare[DIM];
int n,m,q,i,j,x,y,k,idx;

void dfs (int nod, int tata){
    E[++k] = nod;
    poz[nod].first = k;
    fth[nod] = tata;
    level[nod] = 1 + level[tata];
    for (auto vecin : L[nod]){
        if (vecin != tata)
            dfs (vecin,nod);
    }
    poz[nod].second = k;
}

void update (int p, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}

int query (int p){
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}

int get_root (int x){

    for (int p=20;p>=0;p--){
        int y = stramos[p][x];
        if (!y)
            continue;

        if (query(poz[x].first) - query(poz[y].first) == level[x] - level[y])
            x = y;
    }

    return x;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>q;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
        mch[i] = make_pair(x,y);
    }

    dfs (1,0);

    for (i=1;i<=n;i++){
        stramos[0][i] = fth[i];
        v[i] = 1;
    }

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++)
            stramos[i][j] = stramos[i-1][stramos[i-1][j]];

    for (i=1;i<=m;i++){
        cin>>idx;
        int x = mch[idx].first, y = mch[idx].second;
        if (fth[x] == y)
            swap (x,y);

        int root = get_root (x);

        if (stare[y]){ /// disconnect

            v[y] = c[y] = v[root];

            update (poz[y].first,-1);
            update (poz[y].second+1,1);

        } else { /// connect

            v[root] = v[root] + v[y] - c[y];

            update (poz[y].first,1);
            update (poz[y].second+1,-1);

        }

        stare[y] = 1 - stare[y];
    }

    for (;q--;){
        cin>>x;
        cout<<v[get_root(x)]<<"\n";
    }


    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40