Submission #526051

#TimeUsernameProblemLanguageResultExecution timeMemory
526051BackNoobLogičari (COCI21_logicari)C++14
110 / 110
225 ms46208 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 3e5 + 227; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } struct DSU{ vector<int> lab; DSU(){} DSU(int _n) { lab.resize(_n + 7 , -1); } int root(int u) {return lab[u] < 0 ? u : lab[u] = root(lab[u]);}; bool union_root(int u , int v) { u = root(u); v = root(v); if(u == v) return false; if(lab[u] > lab[v]) swap(u , v); lab[u] += lab[v]; lab[v] = u; return true; } } dsu; int n; vector<int> adj[mxN]; pair<int , int> edges[mxN]; bool marked[mxN]; int root; int spec; int dp[mxN][2][2][2][2]; int par[mxN]; void dfs(int u , int pa) { for(int v : adj[u]) { if(v == pa) continue; par[v] = u; dfs(v , u); } } int sol(int u , int now , int pr , int c1 , int c2) { if(u == root && now != c1) return inf; if(u == spec && now != c2) return inf; if(u == spec && pr == true && c1 == true) return inf; int &res = dp[u][now][pr][c1][c2]; if(res != -1) return res; res = inf; bool ok = false; if(pr == true) ok = true; if(u == root && c2 == true) ok = true; if(u == spec && c1 == true) ok = true; ll f1 = now; ll f2 = inf; for(int v : adj[u]) { if(v == par[u]) continue; f1 += sol(v , 0 , now , c1 , c2); f2 = min(f2 , 1LL * sol(v , 1 , now , c1 , c2) - sol(v , 0 , now , c1 , c2)); } if(ok == true) minimize(res , f1); else minimize(res , f1 + f2); return res; } void solve() { cin >> n; for(int i = 1 ; i <= n ; i++) cin >> edges[i].fi >> edges[i].se; dsu = DSU(n); for(int i = 1 ; i <= n ; i++) { if(dsu.union_root(edges[i].fi , edges[i].se) == true) { marked[i] = true; adj[edges[i].fi].pb(edges[i].se); adj[edges[i].se].pb(edges[i].fi); } } for(int i = 1 ; i <= n ; i++) { if(marked[i] == false) { root = edges[i].fi; spec = edges[i].se; } } dfs(root , -1); memset(dp , -1 , sizeof(dp)); int ans = inf; for(int c1 = 0 ; c1 <= 1 ; c1++) for(int c2 = 0 ; c2 <= 1 ; c2++) minimize(ans , sol(root , c1 , 0 , c1 , c2)); if(ans == inf) cout << -1; else cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen(TASK".in" , "r" , stdin); //freopen(TASK".out" , "w" , stdout); int tc = 1; //cin >> tc; while(tc--) { solve(); } 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...