oj.uz

Submission #531883

# Submission time Handle Problem Language Result Execution time Memory
531883 2022-03-01T19:12:41 Z cadmiumsky Synchronization (JOI13_synchronization) C++14
100 / 100
 458 ms 23908 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 19 ms 4172 KB Output is correct
8 Correct 18 ms 4204 KB Output is correct
9 Correct 21 ms 4172 KB Output is correct
10 Correct 241 ms 18336 KB Output is correct
11 Correct 250 ms 18328 KB Output is correct
12 Correct 279 ms 22924 KB Output is correct
13 Correct 155 ms 18188 KB Output is correct
14 Correct 176 ms 17632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 18604 KB Output is correct
2 Correct 162 ms 19916 KB Output is correct
3 Correct 145 ms 21936 KB Output is correct
4 Correct 141 ms 22024 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 5 ms 2892 KB Output is correct
7 Correct 42 ms 4712 KB Output is correct
8 Correct 441 ms 23620 KB Output is correct
9 Correct 458 ms 23748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 21204 KB Output is correct
2 Correct 337 ms 23108 KB Output is correct
3 Correct 329 ms 23136 KB Output is correct
4 Correct 335 ms 23152 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 5 ms 2788 KB Output is correct
6 Correct 38 ms 4272 KB Output is correct
7 Correct 429 ms 19208 KB Output is correct
8 Correct 447 ms 23908 KB Output is correct
9 Correct 318 ms 19388 KB Output is correct
10 Correct 335 ms 18628 KB Output is correct
11 Correct 315 ms 21360 KB Output is correct
12 Correct 326 ms 21356 KB Output is correct
13 Correct 330 ms 23152 KB Output is correct