oj.uz

Submission #531073

# Submission time Handle Problem Language Result Execution time Memory
531073 2022-02-27T16:22:22 Z Alex_tz307 Synchronization (JOI13_synchronization) C++17
100 / 100
 238 ms 24784 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int kLog = 16;
int n, m, q, timer, tin[1 + kN], tout[1 + kN], aib[1 + kN], card[1 + kN], last[1 + kN], anc[1 + kN][1 + kLog];
short act[1 + kN];
vector<int> g[1 + kN];
pair<int, int> edges[1 + kN];

void dfs(int u) {
  tin[u] = ++timer;
  card[u] = 1;
  act[u] = -1;
  for (int i = 1; i <= kLog; ++i) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
    if (anc[u][i] == 0) {
      break;
    }
  }
  for (int v : g[u]) {
    if (v != anc[u][0]) {
      anc[v][0] = u;
      dfs(v);
    }
  }
  tout[u] = timer;
}

void update(int x, int v) {
  for (int i = x; i <= n; i += i & -i) {
    aib[i] += v;
  }
}

int query(int x) {
  int ans = 0;
  for (int i = x; i > 0; i = i & (i - 1)) {
    ans += aib[i];
  }
  return ans;
}

int findRoot(int v) {
  for (int i = kLog; i >= 0; --i) {
    if (anc[v][i] && query(tin[v]) == query(tin[anc[v][i]])) {
      v = anc[v][i];
    }
  }
  return v;
}

void testCase() {
  cin >> n >> m >> q;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
    edges[i] = {u, v};
  }
  dfs(1);
  for (int v = 2; v <= n; ++v) {
    update(tin[v], act[v]);
    update(tout[v] + 1, -act[v]);
  }
  for (int i = 0; i < m; ++i) {
    int d;
    cin >> d;
    int u, v;
    tie(u, v) = edges[d];
    if (anc[u][0] == v) {
      swap(u, v);
    }
    act[v] *= -1;
    if (act[v] == 1) {
      int rootU = findRoot(u);
      card[rootU] += card[v] - last[v];
    } else {
      card[v] = card[findRoot(u)];
      last[v] = card[v];
    }
    update(tin[v], act[v]);
    update(tout[v] + 1, -act[v]);
  }
  for (int i = 0; i < q; ++i) {
    int v;
    cin >> v;
    cout << card[findRoot(v)] << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2824 KB Output is correct
7 Correct 11 ms 4100 KB Output is correct
8 Correct 10 ms 4100 KB Output is correct
9 Correct 11 ms 4120 KB Output is correct
10 Correct 193 ms 17804 KB Output is correct
11 Correct 142 ms 17704 KB Output is correct
12 Correct 200 ms 23880 KB Output is correct
13 Correct 66 ms 17800 KB Output is correct
14 Correct 117 ms 16792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 20352 KB Output is correct
2 Correct 74 ms 20180 KB Output is correct
3 Correct 94 ms 23008 KB Output is correct
4 Correct 89 ms 23016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 1 ms 2684 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 3 ms 2896 KB Output is correct
7 Correct 18 ms 4828 KB Output is correct
8 Correct 238 ms 24784 KB Output is correct
9 Correct 223 ms 24648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 24696 KB Output is correct
2 Correct 167 ms 24048 KB Output is correct
3 Correct 151 ms 24168 KB Output is correct
4 Correct 140 ms 24200 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 13 ms 4224 KB Output is correct
7 Correct 182 ms 18652 KB Output is correct
8 Correct 220 ms 24656 KB Output is correct
9 Correct 89 ms 18748 KB Output is correct
10 Correct 147 ms 17980 KB Output is correct
11 Correct 98 ms 21604 KB Output is correct
12 Correct 97 ms 21576 KB Output is correct
13 Correct 153 ms 24168 KB Output is correct