This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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)
| ~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |