Submission #862163

#	Time	Username	Problem	Language	Result	Execution time	Memory
862163		Cyber_Wolf	Logičari (COCI21_logicari)	C++17	0 / 110	217 ms	56544 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;
	if(adj[src].empty())	ret = 0;
	lg check = 0;
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		if((it == node1 && x) || (it == node2 && y))	check++;
		sum += dfs(it, (b << 1), x, y, src);
	}
	if(check == 2)
	{
		return ret;
	}
	if(b&2)
	{
		if(check)
		{
			ret = 1e18;
			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;
		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 = a;
			node2 = b;
			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, i/2), dfs(1, 1, i, i/2)+1});
	}
	// for(int i = 1; i <= n; i++)
	// {
		// for(int j = 0; j < 4; j++)
		// {
			// for(int k = 0; k < 2; k++)
			// {
				// for(int z = 0; z < 2; z++)
				// {
					// cout << (dp[i][j][k][z] >= 1e17 ? -2 : dp[i][j][k][z]) << ' ';
				// }
			// }
		// }
		// cout << '\n';
	// }
	if(ans >= 1e17)	ans = -1;
	cout << ans << '\n';
}

/*
1 2
2 3
3 1
1 4
   1
*/

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