Submission #1273142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273142		repmann	동기화 (JOI13_synchronization)	C++20	20 / 100	155 ms	29468 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
int N, M, K, Q;
struct Edge
{
  int u, v, sz;
  bool p;
}E[100000];
int A[200001];
struct Node
{
  int p, r, sz;
}DSU[100001];
struct Delta
{
  int i, p, r;
}D[200001];
int d;
vector <int> ST[800001];
inline void Insert(int L, int R, int X, int i = 1, int LC = 1, int RC = K)
{
  if((L > RC) || (LC > R)) return;
  if((L <= LC) && (RC <= R)) {ST[i].push_back(X); return;}
  int S = (LC + RC) >> 1;
  Insert(L, R, X, i << 1, LC, S);
  Insert(L, R, X, i << 1 | 1, S + 1, RC);
  return;
}
inline int Find(int u)
{
  while(u != DSU[u].p) u = DSU[u].p;
  return u;
}
inline void Union(int u, int v)
{
  u = Find(u);
  v = Find(v);
  if(u == v) exit(333);
  if(DSU[u].r < DSU[v].r) swap(u, v);
  if(DSU[u].r == DSU[v].r)
  {
    D[++d] = {u, u, DSU[u].r};
    DSU[u].r++;
  }
  DSU[v].p = u;
  D[++d] = {v, v, DSU[v].r};
  return;
}
inline void Rollback(int cp)
{
  while(d > cp)
  {
    DSU[D[d].i].sz = DSU[DSU[D[d].i].p].sz;
    DSU[D[d].i].p = D[d].p;
    DSU[D[d].i].r = D[d].r;
    d--;
  }
  return;
}
int sz = 2, e;
inline void DFS(int i = 1)
{
  int cp = d;
  for(int x : ST[i]) Union(E[x].u, E[x].v);
  if(i >= K)
  {
    e++;
    E[A[e]].p ^= 1;
//    cout << e << ' ' << sz << '\n';
    if(E[A[e]].p)
    {
      DSU[Find(E[A[e]].u)].sz = sz - E[A[e]].sz; ///das odgovarajuci sajz komponenti
//      cout << "bruh1: " << Find(E[A[e]].u) << '\n';
    }
    else
    {
      DSU[Find(E[A[e]].u)].sz = DSU[Find(E[A[e]].v)].sz = sz; ///u obe komponente upises prethodni ukupni sajz
//      cout << "bruh2: " << Find(E[A[e]].u) << ' ' << Find(E[A[e]].v) << '\n';
    }
    if(i == (K + M - 1)) return;
    if(E[A[e + 1]].p) sz = E[A[e + 1]].sz = DSU[Find(E[A[e + 1]].u)].sz; ///upisi ukupni sajz u sz i u E[A[e]].sz jer ce se razdvojiti
    else sz = DSU[Find(E[A[e + 1]].u)].sz + DSU[Find(E[A[e + 1]].v)].sz; ///saberi sajzove u sz jer ce se spojiti
  }
  else
  {
    DFS(i << 1);
    DFS(i << 1 | 1);
  }
  Rollback(cp);
  return;
}
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;
  for(int i = 1; i <= M; i++) cin >> A[i];
  K = 1;
  while(K < M) K <<= 1;
  for(int i = 1; i <= M; i++)
  {
    E[A[i]].p ^= 1;
    if(!E[A[i]].p) {Insert(E[A[i]].sz, i - 1, A[i]); E[A[i]].sz = 0;}
    else E[A[i]].sz = i;
  }
  for(int i = 1; i < N; i++) if(E[i].p) {Insert(E[i].sz, M, i); E[i].p = E[i].sz = 0;}
  for(int i = 1; i <= N; i++) DSU[i] = {i, 0, 1};
//  cout << "krecemo\n";
  DFS();
  int u;
  while(Q--)
  {
    cin >> u;
    cout << DSU[Find(u)].sz << '\n';
  }

  return 0;
}

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