제출 #1160278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160278		pan	Logičari (COCI21_logicari)	C++20	110 / 110	251 ms	33292 KiB

Main

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const INF = 1e9;
ll root1, root2;
ll dp[100005][2][2][2][2];
vector<ll> adj[100005];

ll par[100005];
ll find(ll x) {return (par[x]==x)?x:par[x]= find(par[x]);}
void unite(ll x, ll y) { if ((x=find(x)) != (y=find(y))) par[y] = x;}

ll dfs(ll x, ll from, ll cur, ll par, ll r1, ll r2)
{
	if (dp[x][cur][par][r1][r2] !=-1) return dp[x][cur][par][r1][r2];
	// check validity of state
	bool flag = 0;
	if (x==root1 && cur != r1) flag = 1;
	if (x==root2 && cur !=r2) flag = 1;
	if (x==root2 && par && r1) flag = 1;
	if (flag) return dp[x][cur][par][r1][r2] = INF;
	// check whether it already has 1 blue eye
	bool have = 0;
	if (par) have = 1;
	if (x==root1 && r2) have = 1;
	if (x==root2 && r1) have = 1;
	ll ans = (cur==1);
	for (ll u: adj[x]) if (from !=u) ans += dfs(u, x, 0, cur, r1,r2);
	if (!have)
	{
		ll v = INF;
		for (ll u: adj[x]) if (from !=u) v = min(v, dfs(u, x, 1, cur, r1, r2) - dfs(u, x, 0, cur, r1,r2));
		ans += v;
	}
	return dp[x][cur][par][r1][r2]= ans;
}


int main()
{
	ll n;
	cin >> n;
	for (ll i=1; i<=n; ++i) for (ll j=0; j<2; ++j) for (ll k=0; k<2; ++k) for (ll r1=0; r1< 2; ++r1) for (ll r2=0; r2< 2; ++r2) dp[i][j][k][r1][r2] = -1;
	for (ll i=1; i<=n; ++i) par[i] = i;
	for (ll i=1; i<=n; ++i)
	{
		ll u, v;
		cin >> u >> v;
		if (find(u)==find(v))
		{
			root1= u;
			root2 = v;
		}
		else
		{
			unite(u, v);
			adj[u].pb(v);
			adj[v].pb(u);
		}
	}
	//show(2);
	ll ans = INF;
	for (ll i=0; i<2; ++i)
	{
		for (ll j=0; j<2; ++j) 
		{
			ans = min(ans, dfs(root1, -1,i , 0, i, j));
		}
	}
	if (ans==INF) cout << -1 << endl;
	else cout << ans << endl;
	
	return 0;
}

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