Submission #862226

#	Time	Username	Problem	Language	Result	Execution time	Memory
862226		Cyber_Wolf	Logičari (COCI21_logicari)	C++17	10 / 110	213 ms	58000 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)	return ret = 1e18;
	if(src == node2 && (b&1) != y)	return ret = 1e18;
	if(~ret)	return ret;
	ret = 1e18;
	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(check+(b >> 1) > 1)
	{
		// cout << src << ' ' << b << ' ' << x << ' ' << y << ' ' << check << '\n';
		// cout << node1 << ' ' << node2 << '\n';
		return ret = 1e18;
	}
	if(b&2)
	{
		if(check)
		{
			ret = 1e18;
			// ret = 0;
			return ret;
		}
		ret = sum;
		return ret;
	}
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		if(it == node1 && !x)	continue;
		if(it == node2 && !y)	continue;
		if(check && it != node1 && it != node2)	continue;
		if((node1 == src && y) || (node2 == src && x))	continue;
		ret = min(ret, dfs(it, (b << 1)|1, x, y, src)-dfs(it, (b << 1), x, y, src)+sum+1);
	}
	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});
	}
	// for(int i = 1; i <= n; i++)
	// {
		// cout << "I: " << i << '\n';
		// for(int j = 0; j < 4; j++)
		// {
			// cout << "J: " << j << '\n';
			// for(int k = 0; k < 2; k++)
			// {
				// cout << "K : " << k << '\n';
				// for(int z = 0; z < 2; z++)
				// {
					// cout << (dp[i][j][k][z] >= 1e17 ? -2 : dp[i][j][k][z]) << '\n';
				// }
			// }
		// }
		// cout << '\n';
	// }
	if(ans >= 1e17)	ans = -1;
	cout << ans << '\n';
}
 
/*
1 2
2 3
3 1
1 4
   1
*/

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