제출 #879244

#제출 시각아이디문제언어결과실행 시간메모리
879244vjudge1Logičari (COCI21_logicari)C++17
10 / 110
17 ms5208 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10, MOD = 998244353; bool is[N]; vector<int> g[N]; int check(int n){ int res = 1e9; for(int i = 0;i < (1 << n);i++){ for(int j = 0;j < n;j++){ if((i >> j) & 1){ is[j + 1] = 1; }else{ is[j + 1] = 0; } } bool ok = true; for(int j = 1;j <= n;j++){ int x = 0; for(int to:g[j]){ x += is[to]; } if(x != 1){ ok = false; break; } } if(ok){ res = min(res,__builtin_popcount(i)); } } if(res == 1e9) res = -1; return res; } int n; void solve(){ for(int i = 1;i <= n;i++){ int x,y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } int res = check(n); if(res == -1){ cout << res; return; } assert(res == n / 2 || res == (n + 1) / 2); cout << res; } void test(){ cin >> n; if(n <= 20){ solve(); return; } if(n % 4){ cout << -1; return; } cout << n / 2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; // cin >> T; for(int i = 1;i <= T;i++) { test(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...