Submission #535568

#	Time	Username	Problem	Language	Result	Execution time	Memory
535568		inksamurai	Logičari (COCI21_logicari)	C++17	110 / 110	150 ms	17228 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3HspL4A ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vec(int);
void print(){cout<<"\n";}
template<class T,class...E>
void print(const T&v,const E&...u){cout<<v<<' ',print(u...);}
// e 
 
const int nax=100000;
const int inf=nax;
int n,root,ru,usd[nax+11];
vi adj[nax+11];
 
void get_root(int v,int par){
	if(root!=-1) return;
	usd[v]=1;
	for(auto u:adj[v]){
		if(u==par) continue;
		if(usd[u]){
			root=v;
			ru=u;
			return;
		}
		get_root(u,v);
	}
}
 
int xru,yru,dp[nax+11][2][2];
 
void affine(int v,int par){
	rep(t,2)rep(t1,2) dp[v][t][t1]=inf;
	if(xru){
		if(yru) dp[v][1][1]=1;
		dp[v][0][1]=0;
		for(auto u:adj[v]){
			if(u==par) continue;
			if(u!=ru){
				if(yru) dp[v][1][1]+=dp[u][0][0];
				dp[v][0][1]+=dp[u][0][1];
			}else{
				if(yru) dp[v][1][1]+=dp[u][1][0];
				dp[v][0][1]+=dp[u][1][yru];
			}
		}
	}else{
		dp[v][0][0]=0;
		if(yru) dp[v][1][0]=1;
		for(auto u:adj[v]){
			if(u==par) continue;
			if(u!=ru){
				dp[v][0][0]+=dp[u][0][1];
				if(yru) dp[v][1][0]+=dp[u][0][0];
			}else{
				dp[v][0][0]+=dp[u][0][yru];
				if(yru) dp[v][1][0]+=dp[u][0][0];
			}
		}
		for(auto u:adj[v]){
			if(u==par or u==ru) continue;
			dp[v][0][1]=min(dp[v][0][1],dp[v][0][0]-dp[u][0][1]+dp[u][1][1]);
			if(yru) dp[v][1][1]=min(dp[v][1][1],dp[v][1][0]-dp[u][0][0]+dp[u][1][0]);
		}
	}
}
 
void quq(int v,int par){
	dp[v][0][0]=0;
	dp[v][1][0]=1;
	bool pok=0;
	for(auto u:adj[v]){
		if(u==par) continue;
		pok=pok or (u==ru);
		quq(u,v);
		dp[v][0][0]+=dp[u][0][1];
		dp[v][1][0]+=dp[u][0][0];
	}
	dp[v][0][1]=dp[v][1][1]=inf;
	for(auto u:adj[v]){
		if(u==par) continue;
		dp[v][0][1]=min(dp[v][0][1],dp[v][0][0]-dp[u][0][1]+dp[u][1][1]);
		dp[v][1][1]=min(dp[v][1][1],dp[v][1][0]-dp[u][0][0]+dp[u][1][0]);
	}
	if(pok){
		affine(v,par);
	}
}
 
signed main(){
_3HspL4A;
	cin>>n;
	rep(i,n){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	root=-1;
	get_root(0,-1);
	{
		rep(i,sz(adj[root])){
			if(adj[root][i]==ru){
				adj[root].erase(adj[root].begin()+i);
				break;
			}
		}
		rep(i,sz(adj[ru])){
			if(adj[ru][i]==root){
				adj[ru].erase(adj[ru].begin()+i);
				break;
			}
		}
	}
	int ans=inf;
	rep(t,2){
		rep(t1,2){
			yru=!t,xru=!t1;
			rep(i,n){
				dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=inf;
			}
			quq(root,-1);
			ans=min(ans,dp[root][t][t1]);
		}
	}
	print(ans>=inf?-1:ans);
//	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50