Submission #491397

#TimeUsernameProblemLanguageResultExecution timeMemory
491397julian33Logičari (COCI21_logicari)C++14
10 / 110
62 ms15080 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=2e5+5; //make sure this is right const int mod=1e9+7; vector<int> graph[mxN]; int done[mxN],blue[mxN],never[mxN],deg[mxN]; void dfs(int at){ int t=0; for(int &i:graph[at]){ if(blue[i]) t=1; } for(int &i:graph[at]){ if(never[i] || blue[i]) continue; if(t){ never[i]=1; dfs(i); } else{ blue[i]=1; dfs(i); } } } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; cin>>n; for(int i=0;i<n;i++){ int a,b; cin>>a>>b; graph[a].pb(b); graph[b].pb(a); deg[a]++; deg[b]++; } queue<int> q; for(int i=1;i<=n;i++){ if(deg[i]==1) q.push(i); } if(!sz(q)){ if(n%4){ cout<<-1<<"\n"; } else{ int ans=0; blue[1]=1; blue[graph[1][0]]=1; dfs(graph[1][0]); for(int i=1;i<=n;i++) ans+=blue[i]; cout<<ans<<"\n"; } return 0; } int ans=0; while(!q.empty()){ int at=q.front(); q.pop(); done[at]=1; ans++; for(int &i:graph[at]){ if(never[i]) continue; blue[i]=1; for(int &j:graph[i]){ if(!done[j]){ done[j]=1; for(int &k:graph[j]){ if(blue[k]) continue; if(!never[k]){ for(int &u:graph[k]){ if(blue[u] || done[u]) continue; deg[u]--; if(!deg[u]){ cout<<-1<<"\n"; return 0; } if(deg[u]==1) q.push(u); } } never[k]=1; } } } } } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...