oj.uz

Submission #474035

# Submission time Handle Problem Language Result Execution time Memory
474035 2021-09-16T16:54:21 Z nicolaalexandra Synchronization (JOI13_synchronization) C++14
100 / 100
 838 ms 25892 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 24 ms 6400 KB Output is correct
8 Correct 23 ms 6428 KB Output is correct
9 Correct 22 ms 6304 KB Output is correct
10 Correct 347 ms 19248 KB Output is correct
11 Correct 335 ms 19256 KB Output is correct
12 Correct 566 ms 25448 KB Output is correct
13 Correct 153 ms 19516 KB Output is correct
14 Correct 221 ms 18896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 22176 KB Output is correct
2 Correct 164 ms 22036 KB Output is correct
3 Correct 182 ms 25180 KB Output is correct
4 Correct 183 ms 25012 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 5 ms 5056 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 7 ms 5196 KB Output is correct
7 Correct 50 ms 7044 KB Output is correct
8 Correct 838 ms 25856 KB Output is correct
9 Correct 823 ms 25812 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 25580 KB Output is correct
2 Correct 446 ms 25600 KB Output is correct
3 Correct 448 ms 25652 KB Output is correct
4 Correct 449 ms 25816 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 7 ms 5196 KB Output is correct
6 Correct 45 ms 6432 KB Output is correct
7 Correct 612 ms 19628 KB Output is correct
8 Correct 797 ms 25892 KB Output is correct
9 Correct 360 ms 20152 KB Output is correct
10 Correct 447 ms 19604 KB Output is correct
11 Correct 389 ms 22848 KB Output is correct
12 Correct 405 ms 22892 KB Output is correct
13 Correct 448 ms 25668 KB Output is correct