Submission #705375

#TimeUsernameProblemLanguageResultExecution timeMemory
705375Chal1shkanLogičari (COCI21_logicari)C++14
0 / 110
7 ms15192 KiB
# include <bits/stdc++.h> # define pb push_back # define ff first # define ss second # define nl "\n" # define sz(x) ((int)(x).size()) # define deb(x) cerr << #x << " = " << x << endl; # define pll pair <ll, ll> typedef long long ll; typedef unsigned long long ull; typedef long double ld; const ll maxn = 1e5 + 25; const ll inf = 2e9 + 0; const ll mod = 1e9 + 123; const ll dx[] = {-1, 1, 0, 0}; const ll dy[] = {0, 0, -1, 1}; using namespace std; ll n, par[maxn]; vector <ll> g[maxn]; ll root, spec; ll dp[maxn][2][2][2][2]; ll find_set (ll v) { if (v == par[v]) return v; return par[v] = find_set(par[v]); } void build (ll v, ll pa) { par[v] = pa; for (ll to : g[v]) { if (to == pa) continue; build(to, v); } } ll solve (ll v, bool col_me, bool col_par, bool col_root, bool col_spec) { if (dp[v][col_me][col_par][col_root][col_spec] != -1) return dp[v][col_me][col_par][col_root][col_spec]; if (v == root && col_me != col_root) return dp[v][col_me][col_par][col_root][col_spec] = inf; if (v == spec && col_me != col_spec) return dp[v][col_me][col_par][col_root][col_spec] = inf; if (v == spec && col_root && col_par) return dp[v][col_me][col_par][col_root][col_spec] = inf; bool boo = 0; if (col_par) boo = 1; if (v == root && col_spec) boo = 1; if (v == spec && col_root) boo = 1; ll sum = col_me; for (ll to : g[v]) { if (to == par[v]) continue; sum += solve(to, 0, col_me, col_root, col_spec); } ll val = inf; if (boo) { val = sum; } else { for (ll to : g[v]) { if (to == par[v]) continue; ll cur = sum - solve(to, 0, col_me, col_root, col_spec) + solve(to, 1, col_me, col_root, col_spec); val = min(val, cur); } } return dp[v][col_me][col_par][col_root][col_spec] = val; } void ma1n (/* SABR */) { cin >> n; for (ll i = 1; i <= n; ++i) { par[i] = i; } memset(dp, -1, sizeof(dp)); for (ll i = 1, u, v; i <= n; ++i) { cin >> u >> v; ll cmp1 = find_set(u); ll cmp2 = find_set(v); if (cmp1 == cmp2) { root = u; spec = v; } else { par[v] = u; g[u].pb(v); g[v].pb(u); } } build(root, -1); // cout << "start" << endl; // cout << root << endl; // for (ll v = 1; v <= n; ++v) // { // cout << v << ' ' << par[v] << endl; // } // cout << "end" << endl; ll ans = inf; ans = min(ans, solve(root, 0, 0, 0, 0)); ans = min(ans, solve(root, 1, 0, 1, 0)); ans = min(ans, solve(root, 0, 0, 0, 1)); ans = min(ans, solve(root, 1, 0, 1, 1)); if (ans == inf) ans = -1; cout << ans << nl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("spainting.in", "r", stdin); // freopen("spainting.out", "w", stdout); int ttt = 1; // cin >> ttt; for (int test = 1; test <= ttt; ++test) { // cout << "Case " << test << ":" << ' '; ma1n(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...