oj.uz

Submission #949137

# Submission time Handle Problem Language Result Execution time Memory
949137 2024-03-19T02:01:16 Z koukirocks Love Polygon (BOI18_polygon) C++17
46 / 100
 2000 ms 18148 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;
	}
	if (n<=20) {
		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";
	} else {
		vector<bool> vis(n,0);
		int ans=0;
		for (int i=0;i<n;i++) {
			if (vis[i]) continue;
			int now=i;
			int st=i;
			int sz=1;
			vis[i]=true;
			while (G[now]!=st) {
//				cout<<now<<" ";
				sz++;
				now=G[now];
				vis[now]=true;
			}
			if (sz==2) continue;
			ans+=(sz+1)>>1;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 348 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 26 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 27 ms 348 KB Output is correct
8 Correct 27 ms 348 KB Output is correct
9 Correct 24 ms 344 KB Output is correct
10 Correct 34 ms 444 KB Output is correct
11 Correct 29 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 106 ms 16660 KB Output is correct
5 Correct 108 ms 13960 KB Output is correct
6 Correct 106 ms 18148 KB Output is correct
7 Correct 105 ms 16520 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 15248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 348 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 26 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 27 ms 348 KB Output is correct
8 Correct 27 ms 348 KB Output is correct
9 Correct 24 ms 344 KB Output is correct
10 Correct 34 ms 444 KB Output is correct
11 Correct 29 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 416 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 106 ms 16660 KB Output is correct
20 Correct 108 ms 13960 KB Output is correct
21 Correct 106 ms 18148 KB Output is correct
22 Correct 105 ms 16520 KB Output is correct
23 Execution timed out 2045 ms 15248 KB Time limit exceeded
24 Halted 0 ms 0 KB -