Submission #705377

#	Time	Username	Problem	Language	Result	Execution time	Memory
705377		Chal1shkan	Logičari (COCI21_logicari)	C++14	110 / 110	220 ms	32760 KiB

Main

# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 1e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 1e9 + 123;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;

ll n, par[maxn];
vector <ll> g[maxn];
ll root, spec;
ll dp[maxn][2][2][2][2];

ll find_set (ll v)
{
	if (v == par[v]) return v;
	return par[v] = find_set(par[v]);
}

void build (ll v, ll pa)
{
	par[v] = pa;
	for (ll to : g[v])
	{
		if (to == pa) continue;
		build(to, v);
	}
}

ll solve (ll v, bool col_me, bool col_par, bool col_root, bool col_spec)
{
	if (dp[v][col_me][col_par][col_root][col_spec] != -1) return dp[v][col_me][col_par][col_root][col_spec];
	if (v == root && col_me != col_root)  return dp[v][col_me][col_par][col_root][col_spec] = inf;
	if (v == spec && col_me != col_spec)  return dp[v][col_me][col_par][col_root][col_spec] = inf;
	if (v == spec && col_root && col_par) return dp[v][col_me][col_par][col_root][col_spec] = inf;
	bool boo = 0;
	if (col_par) boo = 1;
	if (v == root && col_spec) boo = 1;
	if (v == spec && col_root) boo = 1;
	ll sum = (ll)col_me;
	for (ll to : g[v])
	{
		if (to == par[v]) continue;
		sum += solve(to, 0, col_me, col_root, col_spec);
	}
	ll val = inf;
	if (boo)
	{
		val = sum;
	}
	else
	{
		for (ll to : g[v])
		{
			if (to == par[v]) continue;
			ll cur = sum - solve(to, 0, col_me, col_root, col_spec) + solve(to, 1, col_me, col_root, col_spec);
			val = min(val, cur);
		}
	}
	return dp[v][col_me][col_par][col_root][col_spec] = val;
}

void ma1n (/* SABR */)
{
	cin >> n;
	for (ll i = 1; i <= n; ++i)
	{
		par[i] = i;
	}
	memset(dp, -1, sizeof(dp));
	for (ll i = 1, u, v; i <= n; ++i)
	{
		cin >> u >> v;
		ll cmp1 = find_set(u);
		ll cmp2 = find_set(v);
		if (cmp1 == cmp2)
		{
			root = u;
			spec = v;
		}
		else
		{
			par[cmp2] = cmp1;
			g[u].pb(v);
			g[v].pb(u);
		}
	}
	build(root, root);
	ll ans = inf;
	ans = min(ans, solve(root, 0, 0, 0, 0));
	ans = min(ans, solve(root, 1, 0, 1, 0));
	ans = min(ans, solve(root, 0, 0, 0, 1));
	ans = min(ans, solve(root, 1, 0, 1, 1));
	if (ans == inf) ans = -1;
	cout << ans << nl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("spainting.in", "r", stdin);
//  freopen("spainting.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

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