Submission #741233

#TimeUsernameProblemLanguageResultExecution timeMemory
741233Pichon5Logičari (COCI21_logicari)C++17
0 / 110
200 ms30908 KiB
#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <string> #include <sstream> #include <fstream> #include <cmath> #include <queue> #include <stack> #include <unordered_map> #include <unordered_set> #include <bitset> #include <bits/stdc++.h> #define lcm(a,b) (a/__gcd(a,b))*b #define jumanji ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define pb push_back #define F first #define S second #define int long long #define vi vector<int> #define ll long long using namespace std; const int tam=1e5+5; vector<vi>G; int A; int B; bool vis[tam]; //find two nodes inside a cycle void dfs(int u,int p){ vis[u]=1; for(auto v:G[u]){ if(v==p)continue; if(vis[v]){ A=u; B=v; return; } dfs(v,u); } } //dp on tree int dp[tam][2][2][2][2]; int f(int nodo,int color, int cP,int cA, int cB, int p=0){ int &ans=dp[nodo][color][cP][cA][cB]; if(ans!=-1)return ans; if(nodo==A && color!=cA)return ans=1e6; if(nodo==B && color!=cB)return ans=1e6; if(nodo==B && cA && cP)return ans=1e6; // if(G[nodo].size()==1 and nodo!=A){ // return 0; // } //ok cero si mis hijos tienen cero ans=1e6; bool ok=true; if(nodo==B && cA)ok=false; if(cP)ok=false; if(nodo==A && cB)ok=false; //todos tienen que ser cero int sum=0; for(auto v:G[nodo]){ if(v==p)continue; sum+=f(v,0,color,cA,cB,nodo); } if(ok==false){ ans=min(ans,sum); }else{ //solo tengo que pintar uno for(auto v:G[nodo]){ if(v==p)continue; ans=min(ans,sum-f(v,0,color,cA,cB,nodo)+f(v,1,color,cA,cB,nodo)+1); } } return ans; } signed main(){ jumanji memset(dp,-1,sizeof dp); int n,a,b; cin>>n; G.assign(n+1,vi()); vector<pair<int,int>>edges; for(int i=0;i<=n;i++){ cin>>a>>b; G[a].pb(b); G[b].pb(a); edges.pb({a,b}); } dfs(1,0); G.assign(n+1,vi()); for(auto e:edges){ if(e.F==A and e.S==B)continue; if(e.F==B and e.S==A)continue; // cout<<e.F<<" f "<<e.S<<endl; G[e.F].pb(e.S); G[e.S].pb(e.F); } //ambos 1s int res=1e6; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ int curr=f(A,i,0,i,j)+i; res=min(res,curr); } } // cout<<A<<" "<<B<<endl; if(res==1e6){ cout <<-1<<endl; }else{ cout<<res<<endl; } return 0; } //Guess i wont be comming to church on sunday
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...