Submission #658382

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658382	2022-11-13T04:04:17 Z	sam571128	Logičari (COCI21_logicari)	C++17	20 / 110	127 ms	5924 KB

Main

#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";
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	2 ms	2676 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	33 ms	5924 KB	Output is correct
6	Correct	34 ms	5884 KB	Output is correct
7	Correct	32 ms	5868 KB	Output is correct
8	Correct	40 ms	5840 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	2648 KB	Output is correct
2	Correct	99 ms	2656 KB	Output is correct
3	Correct	104 ms	2644 KB	Output is correct
4	Correct	127 ms	2652 KB	Output is correct
5	Correct	1 ms	2644 KB	Output is correct
6	Correct	49 ms	2644 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	24 ms	2564 KB	Output is correct
9	Correct	96 ms	2644 KB	Output is correct
10	Correct	100 ms	2644 KB	Output is correct
11	Correct	13 ms	2668 KB	Output is correct
12	Correct	102 ms	2656 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	2648 KB	Output is correct
2	Correct	99 ms	2656 KB	Output is correct
3	Correct	104 ms	2644 KB	Output is correct
4	Correct	127 ms	2652 KB	Output is correct
5	Correct	1 ms	2644 KB	Output is correct
6	Correct	49 ms	2644 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	24 ms	2564 KB	Output is correct
9	Correct	96 ms	2644 KB	Output is correct
10	Correct	100 ms	2644 KB	Output is correct
11	Correct	13 ms	2668 KB	Output is correct
12	Correct	102 ms	2656 KB	Output is correct
13	Incorrect	2 ms	2676 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	2 ms	2676 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	1 ms	2644 KB	Output is correct
5	Correct	33 ms	5924 KB	Output is correct
6	Correct	34 ms	5884 KB	Output is correct
7	Correct	32 ms	5868 KB	Output is correct
8	Correct	40 ms	5840 KB	Output is correct
9	Correct	100 ms	2648 KB	Output is correct
10	Correct	99 ms	2656 KB	Output is correct
11	Correct	104 ms	2644 KB	Output is correct
12	Correct	127 ms	2652 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct
14	Correct	49 ms	2644 KB	Output is correct
15	Correct	1 ms	2644 KB	Output is correct
16	Correct	24 ms	2564 KB	Output is correct
17	Correct	96 ms	2644 KB	Output is correct
18	Correct	100 ms	2644 KB	Output is correct
19	Correct	13 ms	2668 KB	Output is correct
20	Correct	102 ms	2656 KB	Output is correct
21	Incorrect	2 ms	2676 KB	Output isn't correct
22	Halted	0 ms	0 KB	-