oj.uz

Submission #531879

# Submission time Handle Problem Language Result Execution time Memory
531879 2022-03-01T19:10:24 Z cadmiumsky Synchronization (JOI13_synchronization) C++14
0 / 100
 484 ms 23648 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 20292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 484 ms 23648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -