Submission #862536

#	Time	Username	Problem	Language	Result	Execution time	Memory
862536		mgl_diamond	Logičari (COCI21_logicari)	C++17	110 / 110	178 ms	29080 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define fi first
#define se second
#define ins push_back
#define vec vector
#define FOR(i, l, r) for(int i=l; i<=r; ++i)
#define FORD(i, r, l) for(int i=r; i>=l; --i)
#define FORE(i, v) for(auto &i : v)
#define all(x) (x).begin(), (x).end()
#define file "input"

const int lim = 1e9, nx = 1e5+5;
int n;
vec<int> graph[nx];

bool calc[nx][2][2][2][2];
int root, spec, dp[nx][2][2][2][2];

bool vi[nx];
void prep(int u, int p) {
  vi[u] = 1;
  if (root > 0) return;
  for(int v : graph[u]) if (v != p) {
    if (!vi[v]) prep(v, u);
    else {
      root = v;
      spec = u;
      return;
    }
  }
}

int dfs(int u, bool c, bool p, bool r, bool sp, int par) {
  if (calc[u][c][p][r][sp]) return dp[u][c][p][r][sp];
  calc[u][c][p][r][sp] = 1;
  if (u == root && c != r) return n+1;
  if (u == spec && c != sp) return n+1;
  if (u == spec && p && r) return n+1;

  bool satisfied = 0;
  if (u == root && sp) satisfied = 1;
  if (u == spec && r) satisfied = 1;
  if (p) satisfied = 1;

  int &ret = dp[u][c][p][r][sp];
  ret = c;

  bool covered = p || (u == root && sp) || (u == spec && r);
  if (covered)
  {
    for (int v : graph[u]) if (v ^ par) {
      if (v == root && u == spec) continue;
      if (u == root && v == spec) continue;
      ret += dfs(v, 0, c, r, sp, u);
    }
  }
  else
  {
    int alter = n + 1;
    for (int v : graph[u]) if (v ^ par)
    {
      if (v == root && u == spec) continue;
      if (u == root && v == spec) continue;
      ret += dfs(v, 0, c, r, sp, u);
      alter = min(alter, dfs(v, 1, c, r, sp, u) - dfs(v, 0, c, r, sp, u));
    }
    ret += alter;
  }
  ret = min(ret, n+1);

  return ret;
}

void solve() {
  memset(dp, 0x3f, sizeof(dp));
  cin >> n;

  FOR(i, 1, n) {
    int u, v;
    cin >> u >> v;
    graph[u].ins(v);
    graph[v].ins(u);
  }

  prep(1, 1);
  FOR(i, 1, n)
    FOR(c, 0, 1)
      FOR(p, 0, 1)
        FOR(r, 0, 1)
          FOR(sp, 0, 1)
            dp[i][c][p][r][sp] = n+1;

  int ans = n+1;
  FOR(r, 0, 1)
    FOR(sp, 0, 1) {
      ans = min(ans, dfs(root, r, 0, r, sp, root));
//      if (ans == 2) cout << r << " " << sp << "\n";
    }
  cout << (ans <= n ? ans : -1);
//  cout << dfs(root, root, 0, 0, 0, 0);
//  cout << root << " " << spec << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }

  solve();
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int dfs(int, bool, bool, bool, bool, int)':
Main.cpp:44:8: warning: variable 'satisfied' set but not used [-Wunused-but-set-variable]
   44 |   bool satisfied = 0;
      |        ^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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