Submission #862237

#	Time	Username	Problem	Language	Result	Execution time	Memory
862237		Cyber_Wolf	Logičari (COCI21_logicari)	C++17	110 / 110	202 ms	56632 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define lg long long 
 
const lg N = 2e5+5;
 
vector<lg> adj[N], adj2[N];
lg dp[N][4][2][2], par[N], vis[N], tmp, node1, node2;
 
lg get(lg src)
{
	if(par[src] == src)	return src;
	return par[src] = get(par[src]);
}
 
lg dfs(lg src, lg b, lg x, lg y, lg par = -1)
{
	b &= 3;
	auto&ret = dp[src][b][x][y];
	if(src == node1 && (b&1) != x)	
	{
		// cout << src << ' ' << b << ' ' << x << ' ' << y << '\n';
		// cout << 1e14 << '\n';
		return ret = 1e14;
	}
	if(src == node2 && (b&1) != y)	
	{
		// cout << src << ' ' << b << ' ' << x << ' ' << y << '\n';
		// cout << 1e14 << '\n';
		return ret = 1e14;
	}
	if(~ret)	return ret;
	ret = 1e14;
	lg sum = 0;
	lg check = 0;
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		if(src != node1 && src != node2 && ((it == node1 && x) || (it == node2 && y)))	check++;
		sum += dfs(it, (b << 1), x, y, src);
	}
	if((src == node1 && y) || (src == node2 && x))	check++;
	if(src == node1 || src == node2)
	{
		if(par != node1 && par != node2)	check += b/2;
	}
	else if((b&2))	check++;
	if(check > 1)
	{
		// cout << "FAIL " << src << ' ' << b << ' ' << x << ' ' << y << ' ' << check << ' ' << par << '\n';
		// cout << ret << '\n';
		return ret = 1e14;
	}
	if(b&2)
	{
		ret = sum;
		// cout << "b " << src << ' ' << b << ' ' << x << ' ' << y << ' ' << check << ' ' << par << '\n';
		// cout << ret << '\n';
		return ret;
	}
	lg ox = 1;
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		if(check && it != node1 && it != node2)	continue;
		ox = 0;
		ret = min(ret, dfs(it, (b << 1)|1, x, y, src)-dfs(it, (b << 1), x, y, src)+sum+1);
	}
	if(check && ox)	ret = sum;
	// cout << "a " << src << ' ' << b << ' ' << x << ' ' << y << ' ' << check << ' ' << par << '\n';
	// cout << ret << '\n';
	return ret;
}
 
vector<lg> path;
 
lg odd_cycle(lg src, lg par = -1)
{
	vis[src] = ++tmp;
	for(auto it : adj2[src])
	{
		if(it == par)	continue;
		if(vis[it])
		{
			path.push_back(it);
			return (vis[src]-vis[it]-1)%2;
		}
		if(odd_cycle(it, src))	
		{
			path.push_back(src);
			return true;
		}
	}
	return 0;
}
 
int main()
{
	lg n;
	cin >> n;
	for(int i = 1; i <= n; i++)	par[i] = i;
	for(int i = 0; i < n; i++)
	{
		lg u, v;
		cin >> u >> v;
		int a = get(u), b = get(v);
		adj2[u].push_back(v);
		adj2[v].push_back(u);
		if(a == b)	
		{
			node1 = u;
			node2 = v;
			continue;
		}
		par[a] = b;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(dp, -1, sizeof(dp));
	lg ans = 1e18;
	for(int i = 0; i < 4; i++)
	{
		ans = min({ans, dfs(1, 0, i%2, i/2), dfs(1, 1, i%2, i/2)+1});
	}
	if(ans >= 1e14)	ans = -1;
	cout << ans << '\n';
}
 

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