제출 #1198688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198688		ramzialoulou	Logičari (COCI21_logicari)	C++20	10 / 110	29 ms	6472 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    ++deg[a], ++deg[b];
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return (deg[i] > deg[j]);
  });
  int ans = 0;
  vector<bool> seen(n);
  bool fail = false;
  auto Apply = [&](int u) {
    vector<bool> f(n);
    bool ok = false;
    for (int v : g[u]) {
      f[v] = true;
      ok |= seen[v];
    }
    if (!ok) {
      ans += 1;
      for (int v : g[u]) {
        seen[v] = true;
      }
    }
    int mx = 0, node = -1;
    for (int v : g[u]) {
      bool found = false;
      for (int x : g[v]) {
        found |= f[x];
        found |= seen[x];
      }
      if (!found && deg[v] > mx) {
        mx = deg[v];
        node = v;
      }
    }
    if (node == -1) {
      fail = true;
      return;
    }
    for (int v : g[node]) {
      seen[v] = true;
    }
    ans += 1;
  };
  for (int i : order) {
    if (!seen[i]) {
      Apply(i);
    }
  }
  cout << (fail ? -1 : ans) << "\n";
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50