Submission #916633

#	Time	Username	Problem	Language	Result	Execution time	Memory
916633		penguin133	Love Polygon (BOI18_polygon)	C++17	100 / 100	307 ms	38832 KiB

polygon

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

map <string, int> mp;
int n, cnt = 1;
vector <int> rev[200005];
int nxt[200005];
int vis[200005], cyc[200005], memo[200005][2];
vector <int> v;

void dfs(int x){
	//cerr << x << '\n';
	if(vis[x] == 2)return;
	if(vis[x] == 1){
		cyc[x] = 1;
		int cur = x;
		v.push_back(cur);
		cur = nxt[cur];
		while(cur != x){
			//cerr << cur << ' ';
			cyc[cur] = 1;
			v.push_back(cur), cur = nxt[cur];
		}
		return;
	}
	vis[x] = 1;
	dfs(nxt[x]);
	vis[x] = 2;
}

int dp(int x, int f){
	if(memo[x][f] != -1)return memo[x][f];
	vis[x] = 2;
	if(f){
		int ans = 1, mn = 1e18;
		for(auto i : rev[x]){
			if(cyc[i])continue;
			ans += dp(i, 1);
			mn = min(mn, dp(i, 0) - dp(i, 1));
		}
		if(mn != 1e18)ans += mn;
		return memo[x][f] = ans;
	}
	else{
		int ans = 0;
		for(auto i : rev[x])if(!cyc[i])ans += dp(i, 1);
		return memo[x][f] = ans;
	}
}

int memo2[200005][2][2][2];
int dp2(int pos, bool prv, bool prv2, bool first){
	if(pos == (int)v.size())return prv;
	if(memo2[pos][prv][prv2][first] != -1)return memo2[pos][prv][prv2][first];
	int ans = 1e18;
	if(prv){
		ans = min(ans, dp2(pos + 1, 0, 0, 0) + !prv2 + (pos < (int)v.size() - 1 || !first) + dp(v[pos], 0));
		ans = min(ans, dp2(pos + 1, 1, 0, first) + dp(v[pos], 1));
		return memo2[pos][prv][prv2][first] = ans;
	}
	else{
		ans = min(ans, dp2(pos + 1, 1, 1, (pos == 0)) + dp(v[pos], 0));
		ans = min(ans, dp2(pos + 1, 0, 0, 0) + dp(v[pos], 1));
		return memo2[pos][prv][prv2][first] = ans;
	}
}

void solve(){
	cin >> n;
	memset(memo, -1, sizeof(memo));
	for(int i=1;i<=n;i++){
		string a, b; cin >> a >> b;
		if(mp.find(a) == mp.end())mp[a] = cnt++;
		if(mp.find(b) == mp.end())mp[b] = cnt++;
		nxt[mp[a]] = mp[b];
		rev[mp[b]].push_back(mp[a]);
	}
	if(n%2){
		cout << -1 << '\n';
		return;
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			v.clear();
			dfs(i);
			/*
			if((int)v.size() % 2 == 0){
				vector <int> tmp;
				ans += (int)v.size() == 2 ? 0 : (int)v.size() / 2;
				for(auto j : v)ans += dp(j, 0);
			}
			else{
				ans += (int)v.size() / 2;
				int mn = 1e18;
				vector <int> tmp;
				for(auto j : v){
					ans += dp(j, 0);
					mn = min(mn, (dp(j, 1) - dp(j, 0)));
				}
				ans += mn;
			}
			*/
			for(int i = 0; i < (int)v.size(); i++){
				for(int a=0;a<2;a++){
					for(int b=0;b<2;b++)for(int c=0;c<2;c++)memo2[i][a][b][c] = -1;
				}
			}
			int tmp = dp2(0, 0, 0, 0);
			v.push_back(v[0]);
			for(int i = 0; i < (int)v.size(); i++){
				for(int a=0;a<2;a++){
					for(int b=0;b<2;b++)for(int c=0;c<2;c++)memo2[i][a][b][c] = -1;
				}
			}
			v.erase(v.begin());
			int tmp2 = dp2(0, 0, 0, 0);
			ans += min(tmp, tmp2);
			//cout << ans << '\n';
		}
	}
	cout << ans << '\n';
	
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

polygon.cpp:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main(){
      | ^~~~

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