Submission #862692

#TimeUsernameProblemLanguageResultExecution timeMemory
862692Youssif_ElkadiLogičari (COCI21_logicari)C++17
10 / 110
82 ms26076 KiB
#include <bits/stdc++.h> using namespace std; const long long N = 1e5 + 2, mod = 1e9 + 7; vector<int> adj[N]; vector<int> cy; int dp[N][4], dp2[N][5][5]; bool vis[N]; int par[N]; int n, hi; void cyc(int u) { vis[u] = 1; for (auto v : adj[u]) { if (v == par[u]) continue; par[v] = u; if (vis[v]) hi = v; if (hi) return; cyc(v); } vis[u] = 0; } void calc(int u, int p) { bool flag = 0; int cnt[4] = {}, sum[4] = {}; for (auto v : adj[u]) { if (vis[v] || v == p) continue; calc(v, u); for (int i = 0; i < 4; i++) cnt[i] += (dp[v][i] == -1), sum[i] += dp[v][i]; flag = 1; } if (!flag) { dp[u][3] = dp[u][1] = 0; dp[u][0] = dp[u][2] = -1; return; } for (int i = 0; i < 4; i++) dp[u][i] = mod; for (auto v : adj[u]) { if (vis[v] || v == p) continue; // calc dp[u][0] if (dp[v][1] != -1 && cnt[3] - (dp[v][3] == -1) == 0) dp[u][0] = min(dp[u][0], dp[v][1] + (sum[3] - dp[v][3]) + 2); // calc dp[u][1] if (cnt[3] == 0) dp[u][1] = sum[3]; // calc dp[u][2] if (dp[v][0] != -1 && cnt[2] - (dp[v][2] == -1) == 0) dp[u][2] = min(dp[u][2], dp[v][0] + (sum[2] - dp[v][2])); // calc dp[u][3] if (cnt[2] == 0) dp[u][3] = sum[2]; } for (int i = 0; i < 4; i++) dp[u][i] = (dp[u][i] == mod ? -1 : dp[u][i]); } /* dp[u][0]= one dp[v][1] AND all dp[v][3] (source) dp[u][1]= all dp[v][3] (partner) dp[u][2]= one dp[v][0] AND all dp[v][2] (parent) dp[u][3]= all dp[v][2] (nothing) */ /* states: 0: means i am blue 1: means i am sec blue 2: i am after 1 OR 4 3: i am behind 0 OR 4 4: means i am blue and i dont want partner */ int solve(int ind, int lst, int st) { if (~dp2[ind][lst][st]) return dp2[ind][lst][st]; if (ind == cy.size()) { if (lst == 0 && st == 1) return 0; if (lst == 1 && st == 2) return 0; if (lst == 2 && st == 3) return 0; if (lst == 3 && (st == 0 || st == 4)) return 0; if (lst == 4 && st == 2) return 0; return mod; } int ret = mod; if (ind == 0) { // ret = solve(ind + 1, 4, 4) + dp[cy[ind]][0]; for (int i = 0; i < 5; i++) { if ((i == 2 || i == 3) && dp[cy[ind]][3] != -1) ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][3]); else if (i == 4 && dp[cy[ind]][0] != -1) ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][0]); else if ((i == 0 || i == 1) && dp[cy[ind]][1] != -1) ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][1] + (i == 0) * 2); } } else { if (lst == 0 && dp[cy[ind]][1] != -1) ret = solve(ind + 1, 1, st) + dp[cy[ind]][1]; if (lst == 1 && dp[cy[ind]][3] != -1) ret = solve(ind + 1, 2, st) + dp[cy[ind]][3]; if (lst == 2 && dp[cy[ind]][3] != -1) ret = solve(ind + 1, 3, st) + dp[cy[ind]][3]; if (lst == 3 && dp[cy[ind]][1] != -1) ret = min(ret, solve(ind + 1, 0, st) + dp[cy[ind]][1] + 2); if (lst == 3 && dp[cy[ind]][0] != -1) ret = min(ret, solve(ind + 1, 4, st) + dp[cy[ind]][0]); if (lst == 4 && dp[cy[ind]][3] != -1) ret = min(ret, solve(ind + 1, 2, st) + dp[cy[ind]][3]); } return dp2[ind][lst][st] = ret; } int main() { memset(dp2, -1, sizeof dp2); cin >> n; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } cyc(1); int tmp = hi; int cnt = 0; while (true) { cnt++; if (cnt == 1e5 + 4) { return cout << -1, 0; } cy.push_back(tmp); vis[tmp] = 1; tmp = par[tmp]; if (tmp == hi) break; } for (auto v : cy) calc(v, 0); int tmpp = solve(0, 0, 0); // (2 4 3) // cout << dp[2][0] << " " << dp[4][3] << " " << dp[3][3] << " "; if (tmpp == mod) cout << -1; else cout << tmpp; }

Compilation message (stderr)

Main.cpp: In function 'int solve(int, int, int)':
Main.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     if (ind == cy.size())
      |         ~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...