Submission #377238

#	Time	Username	Problem	Language	Result	Execution time	Memory
377238		soroush	Love Polygon (BOI18_polygon)	C++17	0 / 100	306 ms	21784 KiB

polygon

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , cnt = 0;
map < string , int > mp;
vector < int > in[maxn];
int from[maxn] , to[maxn];
int out[maxn];
int selfloop = 0;
int din[maxn];

set < pii > burn;

void sub1(){
	int ans = 21;
	for(int i = 0 ; i < (1 << n) ; i ++){
		bool ok = 1;
		int mat[25];
		ms(mat , -1);
		for(int j = 0 ; j < n ; j ++){
			if(i & (1 << j)){
				if(from[j] == to[j])ok = 0;
				if(mat[from[j]] ^ -1 and mat[from[j]] ^ to[j])ok = 0;
				mat[from[j]] = to[j];
				if(mat[to[j]] ^ -1 and mat[to[j]] ^ from[j])ok = 0;
				mat[to[j]] = from[j];
			}
		}
		if(ok)ans = min(ans ,n - __builtin_popcount(i));
	}
	dokme(ans);
}

int par[maxn];
int sz[maxn];

int getpar(int v){
	return((par[v] == v) ? v : par[v] = getpar(par[v]));
}

void merge(int v , int u){
	if((u = getpar(u)) == (v = getpar(v)))return;
	par[v] = u;
	sz[u] += sz[v];
}

void sub2(){
	for(int i = 0 ; i < n ; i ++)
		par[i] = i , sz[i] = 1;
	for(int i = 0 ; i < n ; i ++)
		merge(i , out[i]);
	int ans = 0;
	for(int i = 0 ; i < n ; i ++)
		ans += sz[getpar(i)] / 2 , ans += sz[getpar(i)] == 2 , sz[getpar(i)] = 0;
	dokme(n - ans);
}

int h[maxn];

bool dfs(int v){
	bool ok = 1;
	for(auto u : in[v]){
		if(h[u] >= 0)return(0);
		h[u] = h[v] + 1 , ok &= dfs(u);
	}
	return(ok);
}

bool val3(){
	bool ok = 1;
	ms(h , -1);
	for(int i = 0 ; i < n ; i ++)
		if(out[i] == i)
			h[i] = 0 , ok &= dfs(i);
	for(int i = 0 ; i < n ; i ++)
		if(h[i] == -1)
			ok = 0;
	return(ok);	
}

int dp[maxn][3]; // empty par child
bool done[maxn];

int solve(int v){
	done[v] = 1;
	for(auto u : in[v])if(burn.count({v,  u}) == 0)
		solve(u);
	int sum = 0;
	for(auto u : in[v])if(burn.count({v,  u}) == 0){
		dp[v][0] += max(dp[u][0] , dp[u][2]);
		dp[v][1] += max(dp[u][0] , dp[u][2]);
		sum += max(dp[u][0] , dp[u][2]);
	}
	for(auto u : in[v])if(burn.count({v,  u}) == 0){
		dp[v][2] = max(dp[v][2] , sum - max(dp[u][0] , dp[u][2]) + dp[u][1]);
	}
	dp[v][1]++;
	return(max(dp[v][0] , dp[v][2]));
}

void sub3(){
	int ans = 0;
	for(int i = 0 ; i < n ; i ++)
		if(out[i] == i)
			ans += solve(i);
	dokme(n - ans);
}

int Cycle = 0 , mark[maxn] , mark2[maxn];
vector < int > vis , cy;
void cyc(int v){
	mark[v] = 2;
	mark2[v] = 1;
	vis.pb(v);
	for(auto u : in[v]){
		if(mark[u] == 1)cyc(u);
		if(Cycle){
			mark[v] = 3;
			if(Cycle == -1)return;
			cy.pb(v);
			if(Cycle == v+1)Cycle = -1;
			return;
		}
		if(mark[u] == 2){cy.pb(v);Cycle = u+1;return;}
		if(mark[u] == 3)continue;
	}
	mark[v] = 3;
}

bool cycle[maxn];
vector < int > comp[maxn];



int32_t main(){
	migmig;
	cin >> n;
	if(n%2)dokme(-1);
	for(int i = 0 ; i < n ; i ++){
		string a , b;
		cin >> a >> b;
		if(!mp.count(a))mp[a] = cnt++;
		if(!mp.count(b))mp[b] = cnt++;
		int u = mp[a] , v = mp[b];
		from[i] = u , to[i] = v;
		out[u] = v;
		if(u == v)
			selfloop++;
		din[v] ++;
		if(u^v)in[v].pb(u);
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i ++)if(out[i] == i)ans += solve(i);
	for(int i = 0 ; i < n ; i ++)par[i] = i , sz[i] = i;
	for(int i = 0 ; i < n ; i ++)merge(i , out[i]);
	for(int i = 0 ; i < n ; i ++)cycle[i] = 1;
	for(int i = 0 ; i < n ; i ++)if(din[i] != 1)cycle[getpar(i)] = 0;
	for(int i = 0 ; i < n ; i ++){
		if(cycle[getpar(i)])
			ans += sz[getpar(i)] / 2 , ans += sz[getpar(i)] == 2 , sz[getpar(i)] = 0 , done[i] = 1;
	}
	for(int i = 0 ; i < n ; i ++)comp[getpar(i)].pb(i);
	for(int i = 0 ; i < n ; i ++)if(comp[i].size() and !done[i]){
		Cycle = 0;
		cy.clear();
		cyc(i);
		int ki = cy.back();
		for(auto u : cy){
			if(din[u] == 1)ki = u;
		}
		burn.clear();
		burn.insert({ki , out[ki]});
		burn.insert({out[ki] , ki});
		for(auto x: comp[i])done[x] = 1;
	}
	
	cout << n - ans;
	return(0);
}

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