oj.uz

Submission #861739

# Submission time Handle Problem Language Result Execution time Memory
861739 2023-10-16T22:25:54 Z Cyber_Wolf Logičari (COCI21_logicari) C++17
0 / 110
 4 ms 19036 KB 
#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], par[N], vis[N], tmp;

lg get(lg src)
{
	if(par[src] == src)	return src;
	return par[src] = get(par[src]);
}

lg dfs(lg src, lg b, lg par = -1)
{
	b &= 3;
	auto&ret = dp[src][b];
	if(~ret)	return ret;
	ret = 1e18;
	lg sum = 0;
	if(adj[src].empty())	ret = 0;
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		sum += dfs(it, (b << 1), src);
	}
	if(b&2)
	{
		// cout << src << ' ' << b << '\n';
		// cout << sum << '\n';
		ret = sum;
		return ret;
	}
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		ret = min(ret, dfs(it, (b << 1)|1, src)-dfs(it, (b << 1), src)+sum+1);
	}
	// cout << src << ' ' << b << '\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)	continue;
		par[a] = b;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(dp, -1, sizeof(dp));
	if(odd_cycle(1))
	{
		if(path.size() == n)
		{
			cout << "-1\n";
			return 0;
		}
	}
	dfs(1, 0);
	dfs(1, 1);
	cout << min(dp[1][0], dp[1][1]+1) << '\n';
}

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

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:90:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   90 |   if(path.size() == n)
      |      ~~~~~~~~~~~~^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Incorrect 4 ms 19036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Incorrect 4 ms 19036 KB Output isn't correct
5 Halted 0 ms 0 KB -