oj.uz

Submission #949124

# Submission time Handle Problem Language Result Execution time Memory
949124 2024-03-19T01:32:10 Z koukirocks Love Polygon (BOI18_polygon) C++17
21 / 100
 106 ms 18300 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n;
vector<pair<string,string> > eg;
int G[MAX];

int main() {
	speed;
	cin>>n;
	vector<string> dct;
	for (int i=0;i<n;i++) {
		string a,b;
		cin>>a>>b;
		eg.emplace_back(a,b);
		dct.push_back(a);
		dct.push_back(b);
	}
	sort(all(dct));
	dct.resize(unique(all(dct))-dct.begin());
	for (int i=0;i<n;i++) {
		auto [a,b]=eg[i];
		int va=lower_bound(all(dct),a)-dct.begin();
		int vb=lower_bound(all(dct),b)-dct.begin();
		G[va]=vb;
	}
	if (n&1) {
		cout<<"-1\n";
		return 0;
	}
	int ans=n;
	for (int st=0;st<(1<<n);st++) {
		bool flag=true;
		vector<int> cnt(n,0);
		for (int i=0;i<n;i++) {
			if (st&(1<<i)) continue;
			if (G[i]==i) {
				flag=false;
				break;
			}
			int tgt=G[i];
			if (G[tgt]==i) continue;
			if (st&(1<<tgt)) {
				if (cnt[tgt]==0) {
					cnt[tgt]++;
					continue;
				}
			}
			flag=false;
			break;
		}
//		if (flag) cout<<st<<"\n";
		if (flag) ans=min(ans,__builtin_popcount(st));
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 464 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 25 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 25 ms 348 KB Output is correct
8 Correct 26 ms 476 KB Output is correct
9 Correct 22 ms 348 KB Output is correct
10 Correct 27 ms 344 KB Output is correct
11 Correct 29 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 464 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 104 ms 18300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 18068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 464 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 25 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 25 ms 348 KB Output is correct
8 Correct 26 ms 476 KB Output is correct
9 Correct 22 ms 348 KB Output is correct
10 Correct 27 ms 344 KB Output is correct
11 Correct 29 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 464 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 104 ms 18300 KB Output isn't correct
20 Halted 0 ms 0 KB -