oj.uz

Submission #705362

# Submission time Handle Problem Language Result Execution time Memory
705362 2023-03-04T06:37:14 Z Chal1shkan Logičari (COCI21_logicari) C++14
20 / 110
 239 ms 26920 KB 
# 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23772 KB Output is correct
4 Correct 15 ms 23752 KB Output is correct
5 Correct 58 ms 26812 KB Output is correct
6 Correct 43 ms 26848 KB Output is correct
7 Correct 44 ms 26828 KB Output is correct
8 Correct 39 ms 26920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 23796 KB Output is correct
2 Correct 239 ms 23796 KB Output is correct
3 Correct 202 ms 23804 KB Output is correct
4 Correct 204 ms 23800 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 127 ms 23800 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 67 ms 23800 KB Output is correct
9 Correct 192 ms 23800 KB Output is correct
10 Correct 180 ms 23800 KB Output is correct
11 Correct 43 ms 23812 KB Output is correct
12 Correct 201 ms 23800 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 23796 KB Output is correct
2 Correct 239 ms 23796 KB Output is correct
3 Correct 202 ms 23804 KB Output is correct
4 Correct 204 ms 23800 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 127 ms 23800 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 67 ms 23800 KB Output is correct
9 Correct 192 ms 23800 KB Output is correct
10 Correct 180 ms 23800 KB Output is correct
11 Correct 43 ms 23812 KB Output is correct
12 Correct 201 ms 23800 KB Output is correct
13 Incorrect 12 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23772 KB Output is correct
4 Correct 15 ms 23752 KB Output is correct
5 Correct 58 ms 26812 KB Output is correct
6 Correct 43 ms 26848 KB Output is correct
7 Correct 44 ms 26828 KB Output is correct
8 Correct 39 ms 26920 KB Output is correct
9 Correct 211 ms 23796 KB Output is correct
10 Correct 239 ms 23796 KB Output is correct
11 Correct 202 ms 23804 KB Output is correct
12 Correct 204 ms 23800 KB Output is correct
13 Correct 12 ms 23816 KB Output is correct
14 Correct 127 ms 23800 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 67 ms 23800 KB Output is correct
17 Correct 192 ms 23800 KB Output is correct
18 Correct 180 ms 23800 KB Output is correct
19 Correct 43 ms 23812 KB Output is correct
20 Correct 201 ms 23800 KB Output is correct
21 Incorrect 12 ms 23764 KB Output isn't correct
22 Halted 0 ms 0 KB -