Submission #531879

#	Time	Username	Problem	Language	Result	Execution time	Memory
531879		cadmiumsky	Synchronization (JOI13_synchronization)	C++14	0 / 100	484 ms	23648 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;
const int nmax = 1e5 + 5;
vector<int> g[nmax];
pair<int,int> edg[nmax];
int n;

namespace DSU {
  int pin[nmax], pout[nmax], father[nmax][18], inp = 1, state[nmax],
      sz[nmax], isc[nmax];
  void initP(int node, int f) {
    pin[node] = inp++;
    father[node][0] = f;
    for(int i = 1; i < 18; i++)
      father[node][i] = father[father[node][i - 1]][i - 1];
    for(auto x : g[node]) {
      if(x == f)
        continue;
      initP(x, node);
    }
    pout[node] = inp - 1;
  }
  namespace AIB {
    #define lsb(x) (x & -x)
    int tree[nmax];
    void upd(int poz, int val) {
      while(poz <= n) {
        tree[poz] += val;
        poz += lsb(poz);
      }
    }
    void upd(int l, int r, int val) {
      upd(l, val);
      upd(r + 1, -val);
    }
    int query(int poz) {
      int sum = 0;
      while(poz > 0)
        sum += tree[poz], poz -= lsb(poz);
      return sum;
    }
  }
  int findroot(int x) {
    int root = x, val = AIB::query(pin[x]);
    for(int i = 17; i >= 0; i--) {
      if(AIB::query(pin[father[root][i]]) == val) 
        root = father[root][i];
    }
    return root;
  }
  void init() {
    initP(0, 0);
    for(int i = 1; i < n; i++) {
      if(pin[edg[i].first] > pin[edg[i].second])
        swap(edg[i].first, edg[i].second);
    }
    for(int i = 0; i < n; i++) {
      AIB::upd(pin[i], pout[i], 1);
      sz[i] = 1;
    }
  }
  void insert(int e) {
    int x, y;
    tie(x, y) = edg[e];
    x = findroot(x);
    sz[x] += sz[y] - isc[e];
    AIB::upd(pin[y], pout[y], -1);
    return;
  }
  void erase(int e) {
    int x, y;
    tie(x, y) = edg[e];
    x = findroot(x);
    sz[y] = sz[x];
    isc[e] = sz[y];
    AIB::upd(pin[y], pout[y], -1);
  }
  void toggle(int x) {
    state[x] ^= 1;
    if(state[x])
      insert(x);
    else
      erase(x);
  }
};

int main() {
  int m, q;
  cin >> n >> m >> q;
  for(int i = 1, x, y; i < n; i++) {
    cin >>x >> y;
    edg[i] = {--x, --y};
    g[x].push_back(y);
    g[y].push_back(x);
  }
  DSU::init();
  for(int i = 0, x; i < m; i++) {
    cin >> x;
    DSU::toggle(x);
  }
  for(int x, i = 0; i < q; i++) {
    cin >> x;
    cout <<  DSU::sz[DSU::findroot(--x)] << '\n';
  }
}

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