제출 #1188053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188053		kl0989e	Love Polygon (BOI18_polygon)	C++20	100 / 100	171 ms	27792 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;

vi to(maxn);
vector<vi> in(maxn);
vi seen(maxn,0);

int dfs(int cur) {
	seen[cur]=2;
	if (seen[to[cur]]==2) {
		return to[cur];
	}
	return dfs(to[cur]);
}

vector<vi> dp(maxn,vi(2,0));

void dfs2(int cur) {
	int cnt=0;
	for (auto to:in[cur]) {
		if (seen[to]==3) {
			continue;
		}
		dfs2(to);
		cnt+=min(dp[to][0],dp[to][1]+1);
	}
	dp[cur][1]=cnt;
	dp[cur][0]=cnt+1;
	for (auto to:in[cur]) {
		if (seen[to]==3) {
			continue;
		}
		cnt-=min(dp[to][0],dp[to][1]+1);
		dp[cur][0]=min(dp[cur][0],cnt+min(dp[to][0],dp[to][1])+1);
		cnt+=min(dp[to][0],dp[to][1]+1);
	}
}


void dfsset1(int cur) {
	seen[cur]=1;
	for (auto to:in[cur]) {
		if (seen[to]==1) {
			continue;
		}
		dfsset1(to);
	}
}

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	if (n%2) {
		cout << -1 << '\n';
		return 0;
	}
	map<string,int> gt;
	string s,ss;
	int a,b;
	int t=0;
	int ans=0;
	for (int i=0; i<n; i++) {
		cin >> s >> ss;
		if (!gt.count(s)) {
			gt[s]=t++;
		}
		a=gt[s];
		if (!gt.count(ss)) {
			gt[ss]=t++;
		}
		b=gt[ss];
		to[a]=b;
		in[b].pb(a);
	}
	for (int i=0; i<n; i++) {
		if (seen[i]) {
			continue;
		}
		int a=dfs(i);
		if (to[a]==a) {
			seen[a]=3;
			dfs2(a);
			ans+=min(dp[a][0],dp[a][1]+1);
			dfsset1(a);
		}
		else if (to[to[a]]==a) {
			seen[a]=3;
			seen[to[a]]=3;
			dfs2(a);
			dfs2(to[a]);
			ans+=min(dp[a][1]+dp[to[a]][1],min(dp[a][0],dp[a][1]+1)+min(dp[to[a]][0],dp[to[a]][1]+1));
			dfsset1(a);
		}
		else {
			int mn=1e9;
			int temp=to[to[a]];
			to[to[a]]=a;
			seen[a]=3;
			seen[to[a]]=3;
			dfs2(a);
			dfs2(to[a]);
			mn=min(dp[a][1]+dp[to[a]][1]+1,min(dp[a][0],dp[a][1]+1)+min(dp[to[a]][0],dp[to[a]][1]+1));
			seen[a]=0;
			seen[to[a]]=0;
			to[to[a]]=temp;
			a=to[a];
			to[to[a]]=a;
			seen[a]=3;
			seen[to[a]]=3;
			dfs2(a);
			dfs2(to[a]);
			mn=min(mn,min(dp[a][1]+dp[to[a]][1]+1,min(dp[a][0],dp[a][1]+1)+min(dp[to[a]][0],dp[to[a]][1]+1)));
			ans+=mn;
			dfsset1(a);
		}
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25