oj.uz

Submission #1108241

# Submission time Handle Problem Language Result Execution time Memory
1108241 2024-11-03T13:19:53 Z _rain_ Love Polygon (BOI18_polygon) C++14
21 / 100
 298 ms 18884 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);
	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]]++;
	}
	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 286 ms 10832 KB Output is correct
2 Correct 293 ms 10964 KB Output is correct
3 Correct 298 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 281 ms 10968 KB Output is correct
8 Correct 279 ms 10832 KB Output is correct
9 Correct 280 ms 10832 KB Output is correct
10 Correct 298 ms 11000 KB Output is correct
11 Correct 284 ms 10832 KB Output is correct
12 Correct 3 ms 10832 KB Output is correct
13 Correct 2 ms 10956 KB Output is correct
14 Correct 2 ms 10832 KB Output is correct
15 Correct 4 ms 10832 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 2 ms 10976 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Incorrect 103 ms 18884 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 10832 KB Output is correct
2 Correct 293 ms 10964 KB Output is correct
3 Correct 298 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 281 ms 10968 KB Output is correct
8 Correct 279 ms 10832 KB Output is correct
9 Correct 280 ms 10832 KB Output is correct
10 Correct 298 ms 11000 KB Output is correct
11 Correct 284 ms 10832 KB Output is correct
12 Correct 3 ms 10832 KB Output is correct
13 Correct 2 ms 10956 KB Output is correct
14 Correct 2 ms 10832 KB Output is correct
15 Correct 4 ms 10832 KB Output is correct
16 Correct 3 ms 10832 KB Output is correct
17 Correct 2 ms 10976 KB Output is correct
18 Correct 2 ms 10832 KB Output is correct
19 Incorrect 103 ms 18884 KB Output isn't correct
20 Halted 0 ms 0 KB -