Submission #1159890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159890		sasde	Synchronization (JOI13_synchronization)	C++20	100 / 100	174 ms	46188 KiB

synchronization

#include<bits/stdc++.h>
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int tin[N],bit[N],tout[N],q,m,n,t,sz[N],bo[N],up[N][lg+5];
ii b[N];
vector<int>a[N];
void update(int idx,int val){
  while(idx<=n){
    bit[idx]+=val;
    idx+=idx&-idx;
  }
}
int get(int idx){
  int res=0;
  while(idx>0){
    res+=bit[idx];
    idx-=idx&-idx;
  }
  return res;
}
void capnhat(int u,int val){
  // cout <<tin[u]<<" "<<tout[u]+1<<" "<<val<<'\n';
  update(tin[u],val);
  update(tout[u]+1,-val);
}
void dfs(int u,int cha){
    sz[u]=1;
  tin[u]=++t;
  for(int v:a[u]){
    if(v==cha)continue;
    up[v][0]=u;
    dfs(v,u);
  }
  tout[u]=t;
  capnhat(u,1);
}
int findcha(int u){
  int v=get(tin[u]);
       // cout <<v<<" "<<u<<" "<<tin[u]<<'\n';
  // cout <<v<<'\n';
    for(int j=lg;j>=0;--j){
      if(get(tin[up[u][j]])==v){
        u=up[u][j];
    }
    // cout <<up[u][j]<<" ";
  }
  // cout<<'\n';
    return u;
}
bool k[N];
void solve(){
  cin >> n >> m >> q;
  for(int i=1;i<n;++i){
    int u,v;
    cin >> u >> v;
    a[u].emb(v);
    a[v].emb(u);
    b[i]={u,v};
  }
  dfs(1,-1);
  // cout<<'\n';
  for(int j=1;j<=lg;++j)
  for(int i=1;i<=n;++i)up[i][j]=up[up[i][j-1]][j-1];
  for(int j=1;j<=m;++j){
    int i;
    cin >> i;
    int u=b[i].fi;
    int v=b[i].se;
    // cout <<u<<" "<<v<<'\n';
    if(tin[u]>tin[v])swap(u,v);
    k[i]^=1;
    if(k[i]){
      // cout <<u<<" "<<findcha(u)<<'\n';
      sz[findcha(u)]+=sz[v]-bo[v];
      // cout <<v<<" "<<findcha(u)<<'\n';
      capnhat(v,-1);
    }
    else{
      sz[v]=bo[v]=sz[findcha(u)];
      capnhat(v,1);
    }
  }
  // for(int i=1;i<=n;++i)cout <<get(i)<<" "<<bo[i]<<'\n';
  for(int i=1;i<=q;++i){
    int u;
    cin >> u;
    // cout <<findcha(u)<<" ";
    cout <<sz[findcha(u)]<<'\n';
  }
  
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
    cout<<'\n';
}

}

Compilation message (stderr)

synchronization.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main()
      | ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:119:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:120:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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