Submission #705362

#TimeUsernameProblemLanguageResultExecution timeMemory
705362Chal1shkanLogičari (COCI21_logicari)C++14
20 / 110
239 ms26920 KiB
# include <bits/stdc++.h> # define pb push_back # define ff first # define ss second # define nl "\n" # define sz(x) ((int)(x).size()) # define deb(x) cerr << #x << " = " << x << endl; # define pll pair <ll, ll> typedef long long ll; typedef unsigned long long ull; typedef long double ld; const ll maxn = 1e6 + 25; const ll inf = 1e18 + 0; const ll mod = 1e9 + 123; const ll dx[] = {-1, 1, 0, 0}; const ll dy[] = {0, 0, -1, 1}; using namespace std; ll n, col[maxn]; vector <ll> g[maxn]; bool used[maxn]; bool bad; void ok (ll v) { used[v] = 1; ll cnt = 0; for (ll to : g[v]) { cnt += (col[to] == 1); } if (cnt != 1) { bad = 1; } for (ll to : g[v]) { if (!used[to]) { ok(to); } } } void ma1n (/* SABR */) { cin >> n; for (ll i = 1, u, v; i <= n; ++i) { cin >> u >> v; g[u].pb(v); g[v].pb(u); } if (n <= 20) { ll ans = n + 1; for (ll mask = 0; mask < (1LL << n); ++mask) { bad = 0; ll cnt = 0; for (ll i = 0; i < n; ++i) { used[i + 1] = 0; col[i + 1] = 0; if (mask & (1LL << i)) { cnt++; col[i + 1] = 1; } } ok(1); if (!bad) { ans = min(ans, cnt); } } if (ans == n + 1) ans = -1; cout << ans; } else { bool sub1 = 1; for (ll i = 1; i <= n; ++i) { sub1 &= (sz(g[i]) == 2); } if (sub1) { if (n % 4 == 0) { cout << n / 2 << nl; } else { cout << -1 << nl; } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("spainting.in", "r", stdin); // freopen("spainting.out", "w", stdout); int ttt = 1; // cin >> ttt; for (int test = 1; test <= ttt; ++test) { // cout << "Case " << test << ":" << ' '; ma1n(); } 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...