Submission #657308

#	Time	Username	Problem	Language	Result	Execution time	Memory
657308		inksamurai	Love Polygon (BOI18_polygon)	C++17	29 / 100	252 ms	39620 KiB

polygon

#include <bits/stdc++.h>
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()

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){
		cout<<"-1\n";
		return 0;
	}
	
	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));
	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);
		}
		if(sz(cyc)==1){
			return dp[cyc.back()][0];
		}else{
			assert(0);
		}
	};

	// just find one cycle 
	auto dfs=[&](auto self,int v,int par)->void{
		usd[v]=1;
		way.pb(v);
		for(auto u:adj[v]){
			if(usd[u] and u!=par){
				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,v);
			}
		}
		way.pop_back();
	};

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

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