Submission #1201558

#TimeUsernameProblemLanguageResultExecution timeMemory
1201558MighilonLogičari (COCI21_logicari)C++20
110 / 110
123 ms32140 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const int MOD = 1e9 + 7; int n; vector<vi> adj; vi pa; struct DSU{ vi p; vi sz; DSU(int n){ p.resize(n); F0R(i,n)p[i]=i; sz.resize(n); F0R(i,n)sz[i]=1; } int find(int a){ return p[a]==a?a:p[a]=find(p[a]); } bool merge(int a, int b){ int pa=find(a); int pb=find(b); if(pa==pb) return false; if(sz[pa]<sz[pb]) swap(pa,pb); sz[pa]+=sz[pb]; p[pb]=pa; return true; } }; void dfs(int v,int p){ pa[v]=p; trav(u,adj[v]){ if(u==p)continue; dfs(u,v); } } #define int ll int dp[(int)1e5][2][2][2][2]; int rt,sp; int f(int v,int cv,int cf,int cr,int cs){ if(~dp[v][cv][cf][cr][cs]) return dp[v][cv][cf][cr][cs]; bool good=true; if(v==rt&&cr!=cv) good=false; if(v==sp&&cv!=cs) good=false; if(v==sp&&cr&&cf) good=false; if(!good) return dp[v][cv][cf][cr][cs]=1e9; bool ccv=true; // next node to color if(cf)ccv=false; if(v==sp&&cr)ccv=false; if(v==rt&&cs)ccv=false; int cnt=cv; trav(u,adj[v]){ if(u==pa[v]) continue; cnt+=f(u,0,cv,cr,cs); } int res=1e9; if(ccv){ trav(u,adj[v]){ if(u==pa[v])continue; res=min(res,cnt-f(u,0,cv,cr,cs)+f(u,1,cv,cr,cs)); } } else{ res=min(res,cnt); } return dp[v][cv][cf][cr][cs]=res; } void solve(){ cin>>n; memset(dp,-1,sizeof dp); adj.resize(n); pa.resize(n); DSU dsu(n); F0R(i,n){ int a,b; cin>>a>>b; a--,b--; if(!dsu.merge(a,b)){ rt=a; sp=b; } else{ adj[a].pb(b); adj[b].pb(a); } } dfs(rt,rt); int ans=1e9; F0R(i,2)F0R(j,2){ dbg(f(rt,i,0,i,j),i,j); ans=min(ans,f(rt,i,0,i,j)); } if(ans==(int)1e9) cout<<-1<<nl; else cout<<ans<<nl; } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 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...