Submission #1273150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273150		repmann	Synchronization (JOI13_synchronization)	C++20	100 / 100	246 ms	20120 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
int N, M, Q, glob;
struct Edge
{
  int u, v, sz;
  bool p;
}E[100000];
int SIZE[100001], L[100001], R[100001];
int FT[100001];
int UP[20][100001];
vector <int> VG[100001];
inline void Add(int x, int i)
{
  for(; i <= N; i += i & (-i)) FT[i] += x;
  return;
}
inline int Sum(int i)
{
  int ret = 0;
  for(; i; i -= i & (-i)) ret += FT[i];
  return ret;
}
inline void DFS(int node, int parent = 0)
{
  L[node] = ++glob;
  UP[0][node] = parent;
  for(int i = 1; i <= 18; i++) UP[i][node] = UP[i - 1][UP[i - 1][node]];
  for(int x : VG[node]) if(x != parent) DFS(x, node);
  R[node] = glob;
  return;
}
inline int Find(int u)
{
  int v = u, temp = Sum(L[u]);
  if(!temp) return 1;
  for(int i = 18; i >= 0; i--) if(UP[i][v] && (Sum(L[UP[i][v]]) == temp)) v = UP[i][v];
  return v;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> M >> Q;
  for(int i = 1; i < N; i++)
  {
    cin >> E[i].u >> E[i].v;
    VG[E[i].u].push_back(E[i].v);
    VG[E[i].v].push_back(E[i].u);
  }
  DFS(1);
  for(int i = 1; i < N; i++) if(L[E[i].u] > L[E[i].v]) swap(E[i].u, E[i].v);
  for(int i = 1; i <= N; i++) SIZE[i] = 1;
  for(int i = 1; i <= N; i++) Add(+1, L[i]);
  for(int i = 1; i <= N; i++) Add(-1, R[i] + 1);
  for(int i = 1, j; i <= M; i++)
  {
    cin >> j;
    E[j].p ^= 1;
    if(E[j].p)
    {
      int root = Find(E[j].u);
      SIZE[root] += SIZE[E[j].v] - E[j].sz;
      Add(-1, L[E[j].v]);
      Add(+1, R[E[j].v] + 1);
    }
    else
    {
      int root = Find(E[j].u);
      SIZE[E[j].v] = E[j].sz = SIZE[root];
      Add(+1, L[E[j].v]);
      Add(-1, R[E[j].v] + 1);
    }
  }
  int u;
  while(Q--)
  {
    cin >> u;
    cout << SIZE[Find(u)] << '\n';
  }

  return 0;
}

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