oj.uz

Submission #1067506

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

using namespace std;

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

const int N = 1e5 + 5;

int n, m, cnt;
int dep[N];
array<int, 2> a[N];
bool vis[N];
vector<int> g[N];

void dfs(int u, int p) {
  vis[u] = 1;
  bool flg = 0;
  for (int v : g[u]) {
    if (v == p && !flg) {
      flg = 1;
      continue;
    }
    if (!vis[v]) {
      dep[v] = dep[u] + 1;
      dfs(v, u);
    } else if (dep[u] > dep[v]) {
      int c = (dep[u] - dep[v] - 1) & 1;
      ++a[u][c];
      --a[v][c];
      cnt += c;
    }
  }
}

void DFS(int u) {
  vis[u] = 1;
  for (int v : g[u]) {
    if (!vis[v]) {
      DFS(v);
      for (auto j : {0, 1}) {
        a[u][j] += a[v][j];
      }
    }
  }
}

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

  cin >> n >> m;
  while (m--) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      dfs(i, i);
    }
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      DFS(i);
    }
  }
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    res += dep[i] && a[i][1] == cnt && !a[i][0];
  }
  res += cnt == 1;
  cout << res;
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6612 KB Output is correct
2 Correct 33 ms 11612 KB Output is correct
3 Correct 18 ms 6612 KB Output is correct
4 Correct 33 ms 13316 KB Output is correct
5 Correct 3 ms 3420 KB Output is correct
6 Correct 27 ms 9772 KB Output is correct
7 Correct 34 ms 14952 KB Output is correct
8 Correct 33 ms 14932 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6612 KB Output is correct
2 Correct 21 ms 15004 KB Output is correct
3 Correct 22 ms 14940 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 25 ms 10224 KB Output is correct
6 Correct 27 ms 7252 KB Output is correct
7 Correct 35 ms 10588 KB Output is correct
8 Correct 34 ms 12380 KB Output is correct
9 Correct 30 ms 11868 KB Output is correct
10 Correct 29 ms 10332 KB Output is correct
11 Correct 27 ms 7128 KB Output is correct
12 Correct 31 ms 9048 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7972 KB Output is correct
2 Correct 32 ms 14940 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 34 ms 11588 KB Output is correct
5 Correct 33 ms 12624 KB Output is correct
6 Correct 34 ms 11356 KB Output is correct
7 Correct 50 ms 11600 KB Output is correct
8 Correct 51 ms 12476 KB Output is correct
9 Correct 61 ms 10064 KB Output is correct
10 Correct 56 ms 13276 KB Output is correct
11 Correct 48 ms 10328 KB Output is correct
12 Correct 52 ms 13136 KB Output is correct
13 Correct 45 ms 9940 KB Output is correct
14 Correct 49 ms 13908 KB Output is correct
15 Correct 52 ms 13140 KB Output is correct
16 Correct 47 ms 12376 KB Output is correct
17 Correct 46 ms 10324 KB Output is correct
18 Correct 42 ms 10184 KB Output is correct