oj.uz

답안 #658408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658408 2022-11-13T05:45:13 Z Foxyy Logičari (COCI21_logicari) C++17
10 / 110
 32 ms 5748 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);

const int INF = 0x3f3f3f3f;

struct Solver {
	int& n;
	vector<vector<int>>& adj;
	
	void solve() {
		int ans = INF;
		for (int mask = 2; mask < (1 << n); mask++) {
			if (__builtin_popcount(mask) % 2 != 0) continue;
			
			bool valid = true;
			for (int i = 0; i < n; i++) {
				int cnt = 0;
				for (int j : adj[i]) if ((mask >> j) & 1) {
					cnt++;
				}
				if (cnt != 1) {
					valid = false;
					break;
				}
			}
			
			if (valid) {
				ans = min(ans, __builtin_popcount(mask));
			}
		}
		
		if (ans == INF) {
			cout << "-1\n";
		} else {
			cout << ans << '\n';
		}
	}
};

signed main() {
	Foxyy
	
	int T = 1;
//	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		vector<vector<int>> adj(n);
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			a--, b--;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		
		Solver solver{n, adj};
		solver.solve();
	}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 32 ms 5748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 312 KB Output is correct
2 Correct 7 ms 212 KB Output is correct
3 Correct 6 ms 212 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 12 ms 320 KB Output is correct
10 Correct 8 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 324 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 312 KB Output is correct
2 Correct 7 ms 212 KB Output is correct
3 Correct 6 ms 212 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 12 ms 320 KB Output is correct
10 Correct 8 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 324 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 32 ms 5748 KB Output isn't correct
6 Halted 0 ms 0 KB -