oj.uz

Submission #1108242

# Submission time Handle Problem Language Result Execution time Memory
1108242 2024-11-03T13:22:20 Z _rain_ Love Polygon (BOI18_polygon) C++14
46 / 100
 311 ms 18948 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define name "main"

const int N=(int)1e5;
int deg[N+2],to[N+2],u[N+2],v[N+2],n;
string s1[N+2],s2[N+2];
vector<string>nen;

namespace sub1{
	bool check(){
		return n<=20;
	}
	#define BIT(mask,x) (((mask)>>(x))&(1))
	#define MASK(x) ((1)<<(x))
	const int NN=20;
	int dp[MASK(NN)];
	void main_code(){
		memset(dp,0x3f,sizeof dp);
		dp[0]=0;
		int INF=dp[1];
		for(int mask=0;mask<MASK(n);++mask){
			for(int i=1;i<=n;++i){
				if (BIT(mask,i-1)) continue;
				for(int k=i+1;k<=n;++k){
					if (!BIT(mask,k-1)){
						dp[mask|MASK(i-1)|MASK(k-1)]=min(dp[mask|MASK(i-1)|MASK(k-1)],dp[mask]+(to[i]!=k)+(to[k]!=i));
					}
				}
			}
		}
		if (dp[MASK(n)-1]==INF) dp[MASK(n)-1]=-1;
		cout<<dp[MASK(n)-1];
	}
}

namespace sub2{
	bool check(){
		for(int i=1;i<=n;++i){
			if (deg[i]==0) return false;
		}
		return true;
	}
	const int NN=(int)3e5;
	bool used[NN+2];
	void main_code(){
		int ans=0;
		for(int i=1;i<=n;++i){
			int cnt=0;
			for(int j=i;!used[j];j=to[j]) {
				used[j]=true;
				++cnt;
			}
			if (cnt!=2) ans+=(cnt+1)/2;
		}
		cout<<ans<<'\n';
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen(name".inp","r",stdin);
	// freopen(name".out","w",stdout);
	cin>>n;
	if (n%2==1){
		cout<<-1;
		exit(0);
	}
	for(int i=1;i<=n;++i){
		cin>>s1[i]>>s2[i];
		nen.push_back(s1[i]);
		nen.push_back(s2[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<=n;++i){
		u[i]=upper_bound(nen.begin(),nen.end(),s1[i])-nen.begin();
		v[i]=upper_bound(nen.begin(),nen.end(),s2[i])-nen.begin();
		to[u[i]]=v[i];
		deg[v[i]]++;
	}
	// for(int i=1;i<=n;++i) if (deg[i]==0)
	if (sub1::check()){
		sub1::main_code();
		exit(0);
	}
	if (sub2::check()){
		sub2::main_code();
		exit(0);
	}
	exit(0);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 10832 KB Output is correct
2 Correct 304 ms 11000 KB Output is correct
3 Correct 287 ms 10832 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Correct 301 ms 10832 KB Output is correct
8 Correct 291 ms 10832 KB Output is correct
9 Correct 303 ms 10832 KB Output is correct
10 Correct 308 ms 10960 KB Output is correct
11 Correct 308 ms 10960 KB Output is correct
12 Correct 3 ms 10832 KB Output is correct
13 Correct 3 ms 10832 KB Output is correct
14 Correct 3 ms 10832 KB Output is correct
15 Correct 2 ms 10832 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Correct 108 ms 17316 KB Output is correct
5 Correct 105 ms 18884 KB Output is correct
6 Correct 115 ms 18948 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 10832 KB Output is correct
2 Correct 304 ms 11000 KB Output is correct
3 Correct 287 ms 10832 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Correct 301 ms 10832 KB Output is correct
8 Correct 291 ms 10832 KB Output is correct
9 Correct 303 ms 10832 KB Output is correct
10 Correct 308 ms 10960 KB Output is correct
11 Correct 308 ms 10960 KB Output is correct
12 Correct 3 ms 10832 KB Output is correct
13 Correct 3 ms 10832 KB Output is correct
14 Correct 3 ms 10832 KB Output is correct
15 Correct 2 ms 10832 KB Output is correct
16 Correct 4 ms 10832 KB Output is correct
17 Correct 3 ms 10832 KB Output is correct
18 Correct 2 ms 10832 KB Output is correct
19 Correct 108 ms 17316 KB Output is correct
20 Correct 105 ms 18884 KB Output is correct
21 Correct 115 ms 18948 KB Output is correct
22 Correct 2 ms 6736 KB Output is correct
23 Incorrect 116 ms 17092 KB Output isn't correct
24 Halted 0 ms 0 KB -