Submission #626755

#TimeUsernameProblemLanguageResultExecution timeMemory
626755vovamrLogičari (COCI21_logicari)C++17
10 / 110
173 ms18696 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } const int N = 1e5 + 10; ve<int> gr[N]; int v1, v2; ll dp[N][2][2]; int used[N]; inline void dfs1(int v, int p) { used[v] = 1; for (auto &to : gr[v]) { if (to == p) continue; if (used[to]) v1 = v, v2 = to; else dfs1(to, v); } } inline void dfs(int v, int p, const int &t1, const int &t2) { for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; dfs(to, v, t1, t2); } ll sum = 0; // 0, 0 dp[v][0][0] = 0; for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; dp[v][0][0] += dp[to][0][1]; } chmin(dp[v][0][0], iinf * 1ll); // 1, 0 sum = 0; for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; sum += dp[to][0][0]; } dp[v][1][0] = min(iinf * 1ll, sum + 1); // 0, 1 sum = 0; dp[v][0][1] = iinf; for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; sum += dp[to][0][1]; } for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; chmin(dp[v][0][1], sum - dp[to][0][1] + dp[to][1][1]); } // 1, 1 sum = 0; dp[v][1][1] = iinf; for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; sum += dp[to][0][0]; } for (auto &to : gr[v]) { if (to == p) continue; if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue; chmin(dp[v][1][1], 1 + sum - dp[to][0][0] + dp[to][1][0]); } if (v == v1) dp[v][!t1][0] = dp[v][!t1][1] = iinf; else if (v == v2) { dp[v][!t2][0] = dp[v][!t2][1] = iinf; if (t1) dp[v][t2][0] = iinf; else dp[v][t2][1] = iinf; } } inline void solve() { int n; cin >> n; for (int i = 0; i < n; ++i) { int v, u; cin >> v >> u, --v, --u; gr[v].pb(u), gr[u].pb(v); } dfs1(0, 0); ll ans = iinf; for (int t1 : {0, 1}) { for (int t2 : {0, 1}) { for (int i = 0; i < n; ++i) { for (int j : {0, 1}) { for (int k : {0, 1}) { dp[i][j][k] = iinf; } } } dfs(v1, v1, t1, t2); chmin(ans, dp[v1][t1][!t2]); // if (dp[v1][t1][!t2] != iinf) { // cout << v1 + 1 << " " << v2 + 1 << " " << t1 << " " << t2 << " " << dp[v1][t1][!t2] << '\n'; // } } } cout << (ans > n ? -1 : ans); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...