Submission #862536

#TimeUsernameProblemLanguageResultExecution timeMemory
862536mgl_diamondLogičari (COCI21_logicari)C++17
110 / 110
178 ms29080 KiB
#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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...