oj.uz

Submission #240943

# Submission time Handle Problem Language Result Execution time Memory
240943 2020-06-21T17:20:32 Z rajarshi_basu Synchronization (JOI13_synchronization) C++14
100 / 100
 309 ms 23088 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi vector<ll>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define pll pair<ll,ll>
#define il pair<ll,ll>
#define vv vector
#define endl '\n'

using namespace std;

const int MAXN = 1e5+5;

int n,m,q;
int tin[MAXN];
int tout[MAXN];
int sparseTable[MAXN][20];

int side1[MAXN];
int side2[MAXN];

vi g[MAXN];

int T = 0;
void dfs(int x,int p = -1){
    tin[x] = ++T;
    sparseTable[x][0]=p;
    // sparseTable
    for(int i=1;i<17;i++)
        sparseTable[x][i] = sparseTable[sparseTable[x][i-1]][i-1];
    //
    for(auto e: g[x])
        if(e != p)
            dfs(e,x);

    tout[x] = T;
}

int BIT[MAXN];
void update(int i,int v){
    for(;i<=n;i+=i&(-i))BIT[i]+=v;
}
int query(int i){
    int ans=0;
    for(;i>=1;i-=i&(-i))ans+=BIT[i];
    return ans;
}
int findRoot(int x){
    int cur=query(tin[x]);
    for(int i=16;i>=0;i--)if(query(tin[sparseTable[x][i]])==cur)x=sparseTable[x][i];
    return x;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> q;
    ii all[n-1];
    FORE(i,1,n-1){
        int x,y;
        cin >> x >> y;
        all[i] = {x,y};
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1);

    FORE(i,1,n){
        update(tin[i],1);
        update(tout[i]+1,-1);
        side1[i]=1;
    }
    FORE(i,1,n-1)
        if(tin[all[i].ff]>tin[all[i].ss])
            swap(all[i].ff,all[i].ss);

    while(m--){
        int edge;
        cin >> edge;
        int x=all[edge].ff;
        int y=all[edge].ss;
        int z=findRoot(x);
        if(side2[edge]==-1){
            update(tin[y],1);
            update(tout[y]+1,-1);
            side2[edge]=side1[y]=side1[z];
        }
        else{
            update(tin[y],-1);
            update(tout[y]+1,1);
            side1[z]+=side1[y]-side2[edge];
            side2[edge]=-1;
        }
    }
    while(q--){
        int x;
        cin >> x;
        cout << side1[findRoot(x)] << endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 7 ms 2688 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 18 ms 4352 KB Output is correct
8 Correct 17 ms 4352 KB Output is correct
9 Correct 18 ms 4352 KB Output is correct
10 Correct 204 ms 18296 KB Output is correct
11 Correct 218 ms 18436 KB Output is correct
12 Correct 241 ms 22520 KB Output is correct
13 Correct 123 ms 18540 KB Output is correct
14 Correct 165 ms 18432 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 19188 KB Output is correct
2 Correct 107 ms 20340 KB Output is correct
3 Correct 112 ms 22392 KB Output is correct
4 Correct 119 ms 22520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 26 ms 4864 KB Output is correct
8 Correct 302 ms 22716 KB Output is correct
9 Correct 293 ms 22648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 21252 KB Output is correct
2 Correct 172 ms 22904 KB Output is correct
3 Correct 169 ms 23032 KB Output is correct
4 Correct 175 ms 23088 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 21 ms 4352 KB Output is correct
7 Correct 253 ms 18552 KB Output is correct
8 Correct 298 ms 22648 KB Output is correct
9 Correct 125 ms 19052 KB Output is correct
10 Correct 176 ms 19064 KB Output is correct
11 Correct 144 ms 21112 KB Output is correct
12 Correct 141 ms 21236 KB Output is correct
13 Correct 175 ms 23032 KB Output is correct