Submission #1067497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067497		juicy	전압 (JOI14_voltage)	C++17	100 / 100	169 ms	9420 KiB

voltage

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45