oj.uz

Submission #1108169

# Submission time Handle Problem Language Result Execution time Memory
1108169 2024-11-03T07:13:41 Z _rain_ Love Polygon (BOI18_polygon) C++14
21 / 100
 291 ms 20712 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];
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	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];
	}
	if (sub1::check()){
		sub1::main_code();
		exit(0);
	}
	exit(0);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 10832 KB Output is correct
2 Correct 283 ms 10832 KB Output is correct
3 Correct 280 ms 10832 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 10904 KB Output is correct
6 Correct 122 ms 10832 KB Output is correct
7 Correct 284 ms 10892 KB Output is correct
8 Correct 277 ms 10892 KB Output is correct
9 Correct 282 ms 10832 KB Output is correct
10 Correct 291 ms 10832 KB Output is correct
11 Correct 274 ms 10832 KB Output is correct
12 Correct 2 ms 10832 KB Output is correct
13 Correct 2 ms 10832 KB Output is correct
14 Correct 3 ms 10724 KB Output is correct
15 Correct 3 ms 10832 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 10832 KB Output is correct
2 Correct 283 ms 10832 KB Output is correct
3 Correct 280 ms 10832 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 10904 KB Output is correct
6 Correct 122 ms 10832 KB Output is correct
7 Correct 284 ms 10892 KB Output is correct
8 Correct 277 ms 10892 KB Output is correct
9 Correct 282 ms 10832 KB Output is correct
10 Correct 291 ms 10832 KB Output is correct
11 Correct 274 ms 10832 KB Output is correct
12 Correct 2 ms 10832 KB Output is correct
13 Correct 2 ms 10832 KB Output is correct
14 Correct 3 ms 10724 KB Output is correct
15 Correct 3 ms 10832 KB Output is correct
16 Correct 2 ms 10832 KB Output is correct
17 Correct 2 ms 10724 KB Output is correct
18 Correct 2 ms 10832 KB Output is correct
19 Incorrect 102 ms 20712 KB Output isn't correct
20 Halted 0 ms 0 KB -