oj.uz

Submission #590269

# Submission time Handle Problem Language Result Execution time Memory
590269 2022-07-05T17:34:48 Z ShivanshJ Synchronization (JOI13_synchronization) C++17
100 / 100
 410 ms 42768 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5;
const int MAXP=2e4;
const int INF=1e18;
const int MOD=1e9+7;
const int MAXL=18;
class fenwick {
public:
    vector<int>tree;
    fenwick(int n) {
        tree.resize(n+1);
        for(int i=0;i<=n;i++) {
            tree[i]=0;
        }
    }
    void update(int idx,int val) {
        int curr=idx;
        while(curr<tree.size()) {
            tree[curr]+=val;
            curr+=curr-(curr&(curr-1));
        }
    }
    int query(int r) {
        int curr=r,res=0;
        while(curr) {
            res+=tree[curr];
            curr&=(curr-1);
        }
        return res;
    }
};
vector<int>g[MAXN];
vector<int>e[MAXN];
int tin[MAXN],tout[MAXN],clk,par[MAXN][MAXL],infopar[MAXN],infod[MAXN];
void dfs(int a,int p) {
    tin[a]=(++clk);
    par[a][0]=p;
    for(int j=1;j<MAXL;j++) {
        par[a][j]=par[par[a][j-1]][j-1];
    }
    for(int i=0;i<g[a].size();i++) {
        if(g[a][i]==p) {
            continue;
        }
        dfs(g[a][i],a);
    }
    tout[a]=(++clk);
}
int findp(int node,int dist) {
    int curr=node;
    for(int j=0;j<MAXL;j++) {
        if((1LL<<j)&dist) {
            curr=par[curr][j];
        }
    }
    return curr;
}
int sum(int u,int v,fenwick &info) {
    return info.query(tin[v])-info.query(tin[u]);
}
void del(int u,int v,fenwick &info) { //delete u-v
    info.update(tin[v],1);
    info.update(tout[v],-1);
}
void add(int u,int v,fenwick &info) { //add edge
    info.update(tin[v],-1);
    info.update(tout[v],1);
}

int findroot(int a,fenwick &info) {
    int curr=a;
    for(int j=MAXL-1;j>=0;j--) {
        if(!sum(par[curr][j],a,info)) {
            curr=par[curr][j];
        }
    }
    return curr;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cout<<setprecision(6)<<fixed;
    //freopen("disconnect.in","r",stdin);
    //freopen("disconnect.out","w",stdout);
    int n,m,q;
    cin>>n>>m>>q;
    fenwick info(2*n);
    for(int i=0;i<n-1;i++) {
        int a,b;
        cin>>a>>b;
        e[i].push_back(a),e[i].push_back(b);
        g[a].push_back(b),g[b].push_back(a);
    }
    for(int i=1;i<=n;i++) {
        infod[i]=1;
    }
    dfs(1,0);
    for(int i=0;i<n-1;i++) {
        if(tin[e[i][0]]>tin[e[i][1]]) {
            swap(e[i][0],e[i][1]);
        }
        del(e[i][0],e[i][1],info); //delete all edges
    }
    del(0,1,info);
    while(m--) {
        int x;
        cin>>x;
        x--;
        int s=sum(e[x][0],e[x][1],info);
        if(!s) { //edge is there, and now it is to be deleted
            int res=infod[findroot(e[x][0],info)];
            infod[e[x][1]]=infopar[e[x][1]]=res; //setting e[x][1] as new root
            del(e[x][0],e[x][1],info);
        } else {
            int r=findroot(e[x][0],info),res1=infod[r],res2=infod[e[x][1]],c=infopar[e[x][1]];
            infod[r]=res1+res2-c;
            add(e[x][0],e[x][1],info);
        }
    }
    while(q--) {
        int x;
        cin>>x;
        cout<<infod[findroot(x,info)]<<"\n";
    }
    return 0;
}

Compilation message

synchronization.cpp: In member function 'void fenwick::update(long long int, long long int)':
synchronization.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while(curr<tree.size()) {
      |               ~~~~^~~~~~~~~~~~
synchronization.cpp: In function 'void dfs(long long int, long long int)':
synchronization.cpp:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<g[a].size();i++) {
      |                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9736 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 6 ms 9996 KB Output is correct
7 Correct 19 ms 12432 KB Output is correct
8 Correct 20 ms 12500 KB Output is correct
9 Correct 19 ms 12500 KB Output is correct
10 Correct 271 ms 37696 KB Output is correct
11 Correct 293 ms 37600 KB Output is correct
12 Correct 307 ms 41764 KB Output is correct
13 Correct 147 ms 37576 KB Output is correct
14 Correct 184 ms 36312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 38908 KB Output is correct
2 Correct 112 ms 38472 KB Output is correct
3 Correct 125 ms 40400 KB Output is correct
4 Correct 124 ms 40464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9728 KB Output is correct
5 Correct 6 ms 9724 KB Output is correct
6 Correct 7 ms 9996 KB Output is correct
7 Correct 23 ms 12884 KB Output is correct
8 Correct 410 ms 42768 KB Output is correct
9 Correct 351 ms 42528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 42672 KB Output is correct
2 Correct 170 ms 41428 KB Output is correct
3 Correct 169 ms 41596 KB Output is correct
4 Correct 192 ms 41636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 24 ms 12580 KB Output is correct
7 Correct 346 ms 38560 KB Output is correct
8 Correct 346 ms 42556 KB Output is correct
9 Correct 212 ms 38600 KB Output is correct
10 Correct 223 ms 37552 KB Output is correct
11 Correct 149 ms 40040 KB Output is correct
12 Correct 183 ms 40072 KB Output is correct
13 Correct 190 ms 41660 KB Output is correct