oj.uz

Submission #874670

# Submission time Handle Problem Language Result Execution time Memory
874670 2023-11-17T14:25:13 Z MilosMilutinovic 전압 (JOI14_voltage) C++14
100 / 100
 603 ms 56136 KB 
#include <bits/stdc++.h>
 
using namespace std;

struct op {
  int x;
  int y;
  int sx;
  int sy;
  int cx;
  int cy;
  bool b;
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> u(m), v(m);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i];
    --u[i]; --v[i];
  }
  int ans = 0;
  bool bip = true;
  vector<int> f(n);
  vector<int> sz(n, 1);
  vector<int> col(n);
  iota(f.begin(), f.end(), 0);
  stack<op> stk;
  function<int(int)> Get = [&](int x) {
    return f[x] == x ? x : Get(f[x]);
  };
  function<int(int)> Col = [&](int x) {
    return f[x] == x ? col[x] : col[x] ^ Col(f[x]);
  };
  auto Unite = [&](int x, int y) {
    int px = Get(x);
    int py = Get(y);
    int cx = Col(x);
    int cy = Col(y);
    stk.push({px, py, sz[px], sz[py], col[px], col[py], bip});
    if (px == py) {
      if (cx == cy) {
        bip = false;
      }
      return;
    }
    if (sz[px] < sz[py]) {
      swap(px, py);
    }
    col[py] ^= col[px];
    if (cx == cy) {
      col[py] ^= 1;
    }
    f[py] = px;
    sz[px] += sz[py];
  };
  auto Rollback = [&]() {
    op o = stk.top();
    stk.pop();
    int x = o.x;
    int y = o.y;
    f[x] = x;
    f[y] = y;
    sz[x] = o.sx;
    sz[y] = o.sy;
    col[x] = o.cx;
    col[y] = o.cy;
    bip = o.b;
  };
  vector<vector<int>> qs(4 * m);
  function<void(int, int, int, int, int, int)> AddEdge = [&](int x, int l, int r, int ql, int qr, int i) {
    if (ql <= l && r <= qr) {
      qs[x].push_back(i);
      return;
    }
    int mid = (l + r) / 2;
    if (qr <= mid) {
      AddEdge(x << 1, l, mid, ql, qr, i);
    } else if (ql > mid) {
      AddEdge(x << 1 | 1, mid + 1, r, ql, qr, i);
    } else {
      AddEdge(x << 1, l, mid, ql, qr, i);
      AddEdge(x << 1 | 1, mid + 1, r, ql, qr, i);
    }
  };
  function<void(int, int, int)> Solve = [&](int x, int l, int r) {
    for (int i : qs[x]) {
      Unite(u[i], v[i]);
    }
    if (l == r) {
      if (bip && (Get(u[l]) != Get(v[l]) || Col(u[l]) == Col(v[l]))) {
        ans += 1;
      }
      for (int i : qs[x]) {
        Rollback();
      }
      return;
    }
    int mid = (l + r) / 2;
    Solve(x << 1, l, mid);
    Solve(x << 1 | 1, mid + 1, r);
    for (int i : qs[x]) {
      Rollback();
    }
  };
  for (int i = 0; i < m; i++) {
    if (i > 0) {
      AddEdge(1, 0, m - 1, 0, i - 1, i);
    }
    if (i + 1 < m) {
      AddEdge(1, 0, m - 1, i + 1, m - 1, i);
    }
  }
  Solve(1, 0, m - 1);
  cout << ans << '\n';
  return 0;
}

Compilation message

voltage.cpp: In lambda function:
voltage.cpp:97:16: warning: unused variable 'i' [-Wunused-variable]
   97 |       for (int i : qs[x]) {
      |                ^
voltage.cpp:105:14: warning: unused variable 'i' [-Wunused-variable]
  105 |     for (int i : qs[x]) {
      |              ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 28200 KB Output is correct
2 Correct 302 ms 28504 KB Output is correct
3 Correct 153 ms 28368 KB Output is correct
4 Correct 290 ms 28112 KB Output is correct
5 Correct 22 ms 3420 KB Output is correct
6 Correct 277 ms 28356 KB Output is correct
7 Correct 311 ms 28112 KB Output is correct
8 Correct 334 ms 28364 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 27856 KB Output is correct
2 Correct 141 ms 28356 KB Output is correct
3 Correct 149 ms 28416 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 222 ms 23672 KB Output is correct
6 Correct 233 ms 28112 KB Output is correct
7 Correct 311 ms 28416 KB Output is correct
8 Correct 277 ms 28380 KB Output is correct
9 Correct 312 ms 28624 KB Output is correct
10 Correct 284 ms 28368 KB Output is correct
11 Correct 216 ms 28376 KB Output is correct
12 Correct 268 ms 28384 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 55112 KB Output is correct
2 Correct 306 ms 55896 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 334 ms 30228 KB Output is correct
5 Correct 333 ms 30416 KB Output is correct
6 Correct 291 ms 30104 KB Output is correct
7 Correct 577 ms 56136 KB Output is correct
8 Correct 492 ms 55880 KB Output is correct
9 Correct 493 ms 55892 KB Output is correct
10 Correct 490 ms 55760 KB Output is correct
11 Correct 415 ms 55896 KB Output is correct
12 Correct 485 ms 56064 KB Output is correct
13 Correct 425 ms 55876 KB Output is correct
14 Correct 603 ms 55908 KB Output is correct
15 Correct 482 ms 55900 KB Output is correct
16 Correct 486 ms 55632 KB Output is correct
17 Correct 517 ms 55688 KB Output is correct
18 Correct 421 ms 55880 KB Output is correct