Submission #240150

#	Time	Username	Problem	Language	Result	Execution time	Memory
240150		quocnguyen1012	Synchronization (JOI13_synchronization)	C++14	100 / 100	348 ms	21608 KiB

synchronization

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int a[maxn], tin[maxn], tout[maxn], last[maxn];
vector<int> adj[maxn];
ii edge[maxn];
int par[maxn][20];
int N, M, Q;
bool active[maxn];
int bit[maxn];

void upd(int i, int v)
{
  for(; i <= N; i += i & -i)
    bit[i] += v;
}

void rupd(int l, int r, int v)
{
  upd(l, v); upd(r + 1, -v);
}

int sum(int i)
{
  int res = 0;
  for(; i; i -= i & -i)
    res += bit[i];
  return res;
}

void prepare(int u, int p = -1)
{
  static int nTime = 0;
  tin[u] = ++nTime;
  for(int i = 1; i < 20; ++i)
    par[u][i] = par[par[u][i - 1]][i - 1];
  a[u] = 1;
  for(int v : adj[u]) if(v != p){
    par[v][0] = u;
    prepare(v, u);
  }
  tout[u] = nTime;
}

int root(int u)
{
  for(int i = 19; i >= 0; --i){
    if(par[u][i] && sum(tin[par[u][i]]) == sum(tin[u]))
      u = par[u][i];
  }
  return u;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL

  cin >> N >> M >> Q;
  for(int i = 1; i < N; ++i){
    cin >> edge[i].fi >> edge[i].se;
    adj[edge[i].fi].eb(edge[i].se);
    adj[edge[i].se].eb(edge[i].fi);
  }
  prepare(1);
  for(int i = 2; i <= N; ++i){
    rupd(tin[i], tout[i], 1);
  }
  for(int i = 1; i <= M; ++i){
    int id; cin >> id;
    int u = edge[id].fi, v = edge[id].se;
    if(par[u][0] == v) swap(u, v);
    if(active[id]){
      a[v] = last[v] = a[root(u)];
      rupd(tin[v], tout[v], 1);
    }
    else{
      a[root(u)] += a[v] - last[v];
      rupd(tin[v], tout[v], -1);
    }
    active[id] = !active[id];
  }
  while(Q--){
    int u; cin >> u;
    cout << a[root(u)] << '\n';
  }
}

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