Submission #545559

#	Time	Username	Problem	Language	Result	Execution time	Memory
545559		ivan_tudor	Synchronization (JOI13_synchronization)	C++14	100 / 100	505 ms	24632 KiB

synchronization

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int in[N], out[N];
int aib[N];
void update(int poz, int val){
  for(int i = poz; i < N; i+= i &(-i))
    aib[i]+=val;
}
int query(int poz){
  int ans = 0;
  for(int i = poz; i >0; i-= i&(-i)){
    ans+= aib[i];
  }
  return ans;
}
struct edgesstr{
  int x, y;
};
edgesstr edg[N];
vector<int> gr[N];
int par[17][N];
int inters[N];
bool activ[N];
int ans[N];

void dfs_init(int nod, int dad, int &cnt){
  par[0][nod] = dad;
  for(int log = 1; log<17; log++){
    par[log][nod] = par[log - 1][par[log - 1][nod]];
  }
  in[nod] = ++ cnt;
  for(auto x:gr[nod]){
    if(dad == x)
      continue;
    dfs_init(x, nod, cnt);
  }
  out[nod] = cnt;
}
int find_high(int nod){
  int rsp = nod;
  int tp = query(in[nod]);
  for(int p2 = 16; p2>=0; p2--){
    int sus = par[p2][rsp];
    if(sus != 0 && query(in[sus]) == tp)
      rsp = sus;
  }
  return rsp;
}
void break_edge(int id){
  int a = edg[id].x;
  int b = edg[id].y;
  if(in[a] > in[b])
    swap(a, b);
  a = find_high(a);
  inters[id] = ans[a];
  update(in[b], 1);
  update(out[b] + 1, -1);
  ans[b] = ans[a];
  activ[id] = false;
}

void join_edge(int id){
  int a = edg[id].x;
  int b = edg[id].y;
  if(in[a] > in[b])
    swap(a, b);
  a = find_high(a);
  int newval = ans[a] + ans[b] - inters[id];
  update(in[b], -1);
  update(out[b] + 1, +1);
  ans[a] = newval;
  ans[b] = 0;
  activ[id] = true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin>>n>>m>>q;
    for(int i = 1; i<n; i++){
      int x, y;
      cin>>x>>y;
      edg[i] = {x, y};
      gr[x].push_back(y);
      gr[y].push_back(x);

    }
    int cnt = 0;
    dfs_init(1, 0, cnt);
    for(int i = 1; i<n; i++){
      break_edge(i);
    }
    for(int i = 1; i<=n; i++)
      ans[i] = 1;
    for(int i = 1; i<=m; i++){
      int id;
      cin>>id;
      if(activ[id] == false)
        join_edge(id);
      else
        break_edge(id);
    }
    for(int i = 1; i<=q; i++){
      int c;
      cin>>c;
      cout<<ans[find_high(c)]<<"\n";
    }
    return 0;
}

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