Submission #590269

#	Time	Username	Problem	Language	Result	Execution time	Memory
590269		ShivanshJ	Synchronization (JOI13_synchronization)	C++17	100 / 100	410 ms	42768 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40