oj.uz

Submission #1067495

# Submission time Handle Problem Language Result Execution time Memory
1067495 2024-08-20T18:20:10 Z juicy 전압 (JOI14_voltage) C++17
0 / 100
 48 ms 9156 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]) {
    lab[e[0]] -= 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2584 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2516 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Runtime error 3 ms 4700 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5332 KB Output is correct
2 Runtime error 18 ms 8912 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5076 KB Output is correct
2 Runtime error 16 ms 8888 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7364 KB Output is correct
2 Correct 48 ms 8128 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Runtime error 18 ms 9156 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -