Submission #1067506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067506		juicy	전압 (JOI14_voltage)	C++17	100 / 100	61 ms	15004 KiB

voltage

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