oj.uz

Submission #1067497

# Submission time Handle Problem Language Result Execution time Memory
1067497 2024-08-20T18:22:22 Z juicy 전압 (JOI14_voltage) C++17
100 / 100
 169 ms 9420 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, M = 2e5 + 5;

int n, m, res, valid;
int a[M], b[M], lab[N], c[N];
vector<array<int, 3>> his;

array<int, 2> find(int u) {
  int x = 0;
  while (lab[u] > 0) {
    x ^= c[u];
    u = lab[u];
  }
  return {u, x};
}

void mrg(int u, int v, int w) {
  auto [x, a] = find(u);
  auto [y, b] = find(v);
  if ((u = x) == (v = y)) {
    his.push_back({-1, -1, valid});
    valid &= a ^ b ^ w ^ 1;
    return;
  }
  if (lab[u] > lab[v]) {
    swap(u, v);
  }
  his.push_back({v, lab[v], valid});
  lab[u] += lab[v];
  lab[v] = u;
  c[v] = a ^ b ^ w;
}

void restore() {
  auto e = his.back(); his.pop_back();
  if (~e[0]) {
    int u = lab[e[0]];
    lab[u] -= e[1];
    lab[e[0]] = e[1];
    c[e[0]] = 0;
  }
  valid = e[2];
}

void dc(int l, int r) {
  if (l == r) {
    mrg(a[l], b[l], 0);
    res += valid;
    restore();
    return;
  }
  int md = (l + r) / 2;
  for (int i = l; i <= md; ++i) {
    mrg(a[i], b[i], 1);
  }
  dc(md + 1, r);
  for (int i = l; i <= md; ++i) {
    restore();
  }
  for (int i = md + 1; i <= r; ++i) {
    mrg(a[i], b[i], 1);
  }
  dc(l, md);
  for (int i = md + 1; i <= r; ++i) {
    restore();
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> a[i] >> b[i];
  }
  fill(lab + 1, lab + n + 1, -1);
  valid = 1;
  dc(1, m);
  cout << res;
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4308 KB Output is correct
2 Correct 80 ms 4308 KB Output is correct
3 Correct 38 ms 5308 KB Output is correct
4 Correct 81 ms 5332 KB Output is correct
5 Correct 7 ms 2904 KB Output is correct
6 Correct 78 ms 5308 KB Output is correct
7 Correct 82 ms 5328 KB Output is correct
8 Correct 80 ms 5328 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4304 KB Output is correct
2 Correct 32 ms 4308 KB Output is correct
3 Correct 33 ms 5328 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 64 ms 5088 KB Output is correct
6 Correct 59 ms 5328 KB Output is correct
7 Correct 81 ms 5332 KB Output is correct
8 Correct 77 ms 5332 KB Output is correct
9 Correct 80 ms 5328 KB Output is correct
10 Correct 76 ms 5328 KB Output is correct
11 Correct 57 ms 5328 KB Output is correct
12 Correct 74 ms 5332 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7240 KB Output is correct
2 Correct 53 ms 6000 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 86 ms 4304 KB Output is correct
5 Correct 89 ms 5588 KB Output is correct
6 Correct 83 ms 5588 KB Output is correct
7 Correct 143 ms 8116 KB Output is correct
8 Correct 131 ms 9412 KB Output is correct
9 Correct 129 ms 9416 KB Output is correct
10 Correct 112 ms 9332 KB Output is correct
11 Correct 100 ms 9420 KB Output is correct
12 Correct 120 ms 8144 KB Output is correct
13 Correct 109 ms 9396 KB Output is correct
14 Correct 169 ms 8644 KB Output is correct
15 Correct 115 ms 8132 KB Output is correct
16 Correct 135 ms 8112 KB Output is correct
17 Correct 125 ms 9416 KB Output is correct
18 Correct 117 ms 8644 KB Output is correct