Submission #658382

#TimeUsernameProblemLanguageResultExecution timeMemory
658382sam571128Logičari (COCI21_logicari)C++17
20 / 110
127 ms5924 KiB
#include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); #define int long long using namespace std; const int N = 1e5+5; vector<int> adj[N]; int color[N]; signed main(){ fastio int n; cin >> n; for(int i = 1;i <= n;i++){ int u,v; cin >> u >> v; u--,v--; adj[u].push_back(v); adj[v].push_back(u); } if(n <= 20){ int mn = 1e18; for(int i = 0; i < (1<<n); i++){ bool ok = true; for(int j = 0; j < n; j++){ color[j] = 0; } for(int j = 0; j < n; j++){ if(i & (1<<j)) color[j] = 1; } for(int j = 0; j < n; j++){ int cnt = 0; for(auto v : adj[j]){ if(color[v]) cnt++; } if(cnt != 1) ok = false; } if(ok) mn = min(mn, (int)__builtin_popcount(i)); } cout << (mn==1e18 ? -1 : mn) << "\n"; }else{ cout << (n%4==0 ? 2*n/4 : -1) << "\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...