Submission #657416

#	Time	Username	Problem	Language	Result	Execution time	Memory
657416		inksamurai	Love Polygon (BOI18_polygon)	C++17	100 / 100	233 ms	43624 KiB

polygon

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3NRqilq ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define all(a) a.begin(),a.end()
#define nare {cout<<"-1\n";exit(0);}

const int inf=1e9;

signed main(){
_3NRqilq;
	int m;
	cin>>m;

	vec(pair<string,string>) _es;
	vec(string) tmp;
	rep(i,m){
		string s,t;
		cin>>s>>t;
		tmp.pb(s);
		tmp.pb(t);
		_es.pb({s,t});
	}
	
	sort(all(tmp));
	tmp.erase(unique(all(tmp)),tmp.end());
	int n=sz(tmp);

	if(n%2){
		nare;
	}
	
	vec(vi) adj(n),radj(n);
	rep(i,m){
		auto [s,t]=_es[i];
		int u=lower_bound(all(tmp),s)-tmp.begin();
		int v=lower_bound(all(tmp),t)-tmp.begin();
		adj[u].pb(v);
		radj[v].pb(u);
	}
	
	vi usd(n);
	vi way,cyc;
	vi incyc(n);
	vec(vi) dp(n,vi(2));
	vi edp(n);
	auto fout_cycle=[&]()->int{
		auto dfs=[&](auto self,int v)->void{
			usd[v]=1;
			dp[v][0]+=1;
			int now=0,mi=0;
			for(auto u:radj[v]){
				if(incyc[u]) continue;
				self(self,u);
				now+=dp[u][0];
				mi=min(mi,-dp[u][0]+dp[u][1]);
			}
			dp[v][0]+=now+mi;
			dp[v][1]=now;
		};
		for(auto v:cyc){
			incyc[v]=1;
		}
		for(auto v:cyc){
			dfs(dfs,v);
		}
		for(auto v:cyc){
			edp[v]=0; // dp(v,0) but is disconnected from child
			for(auto u:radj[v]){
				if(incyc[u]) continue;
				edp[v]+=dp[u][0];
			}
		}
		int res=0;
		if(sz(cyc)==1){
			res=dp[cyc.back()][0];
		}else{
			int s=cyc[0];
			int t=cyc.back();
			if(sz(cyc)==2){
				res=min(dp[s][1]+dp[t][1],dp[s][0]+dp[t][0]);
			}else{
				// (s,t) are connected
				{
					vi fdp(2,inf);
					rep(i,sz(cyc)-1){
						int v=cyc[i];
						vi gdp(2,inf);
						if(!i){
							gdp[0]=edp[v]+1;
							gdp[1]=inf;
						}else{
							// last was 1
							gdp[0]=min(gdp[0],fdp[1]+edp[v]+1);
							// last was 0
							gdp[0]=min(gdp[0],fdp[0]+dp[v][0]);
							gdp[1]=min(gdp[1],fdp[0]+dp[v][1]);
						}
						fdp=gdp;
					}
					res=dp[t][1]+fdp[0];
				}
				// (s,t) are disconnected
				{
					vi fdp(2,inf);
					rep(i,sz(cyc)){
						int v=cyc[i];
						vi gdp(2,inf);
						if(!i){
							gdp[0]=dp[v][0];
							gdp[1]=dp[v][1];
						}else{
							// last was 1
							gdp[0]=min(gdp[0],fdp[1]+edp[v]+1);
							// last was 0
							gdp[0]=min(gdp[0],fdp[0]+dp[v][0]);
							gdp[1]=min(gdp[1],fdp[0]+dp[v][1]);
						}
						fdp=gdp;
					}
					res=min(res,fdp[0]);
				}
			}
		}
		return res;
	};

	// just find one cycle 
	auto dfs=[&](auto self,int v)->void{
		usd[v]=1;
		way.pb(v);
		for(auto u:adj[v]){
			if(usd[u]){
				if(!sz(cyc)){
					per(i,sz(way)){
						cyc.pb(way[i]);
						if(way[i]==u) break;
					}
					reverse(all(cyc));
				}
				return;
			}
			if(!usd[u]){
				self(self,u);
			}
		}
		way.pop_back();
	};

	int ans=0;
	rep(rt,n){
		if(usd[rt]) continue;
		way.clear();
		cyc.clear();
		dfs(dfs,rt);
		ans+=fout_cycle();
	}
	print(ans);
}

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