# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
# define pll pair <ll, ll>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 1e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 1e9 + 123;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
using namespace std;
ll n, par[maxn];
vector <ll> g[maxn];
ll root, spec;
ll dp[maxn][2][2][2][2];
ll find_set (ll v)
{
if (v == par[v]) return v;
return par[v] = find_set(par[v]);
}
void build (ll v, ll pa)
{
par[v] = pa;
for (ll to : g[v])
{
if (to == pa) continue;
build(to, v);
}
}
ll solve (ll v, bool col_me, bool col_par, bool col_root, bool col_spec)
{
if (dp[v][col_me][col_par][col_root][col_spec] != -1) return dp[v][col_me][col_par][col_root][col_spec];
if (v == root && col_me != col_root) return dp[v][col_me][col_par][col_root][col_spec] = inf;
if (v == spec && col_me != col_spec) return dp[v][col_me][col_par][col_root][col_spec] = inf;
if (v == spec && col_root && col_par) return dp[v][col_me][col_par][col_root][col_spec] = inf;
bool boo = 0;
if (col_par) boo = 1;
if (v == root && col_spec) boo = 1;
if (v == spec && col_root) boo = 1;
ll sum = col_me;
for (ll to : g[v])
{
if (to == par[v]) continue;
sum += solve(to, 0, col_me, col_root, col_spec);
}
ll val = inf;
if (boo)
{
val = sum;
}
else
{
for (ll to : g[v])
{
if (to == par[v]) continue;
ll cur = sum - solve(to, 0, col_me, col_root, col_spec) + solve(to, 1, col_me, col_root, col_spec);
val = min(val, cur);
}
}
return dp[v][col_me][col_par][col_root][col_spec] = val;
}
void ma1n (/* SABR */)
{
cin >> n;
for (ll i = 1; i <= n; ++i)
{
par[i] = i;
}
memset(dp, -1, sizeof(dp));
for (ll i = 1, u, v; i <= n; ++i)
{
cin >> u >> v;
ll cmp1 = find_set(u);
ll cmp2 = find_set(v);
if (cmp1 == cmp2)
{
root = u;
spec = v;
}
else
{
par[v] = u;
g[u].pb(v);
g[v].pb(u);
}
}
build(root, -1);
// cout << "start" << endl;
// cout << root << endl;
// for (ll v = 1; v <= n; ++v)
// {
// cout << v << ' ' << par[v] << endl;
// }
// cout << "end" << endl;
ll ans = inf;
ans = min(ans, solve(root, 0, 0, 0, 0));
ans = min(ans, solve(root, 1, 0, 1, 0));
ans = min(ans, solve(root, 0, 0, 0, 1));
ans = min(ans, solve(root, 1, 0, 1, 1));
if (ans == inf) ans = -1;
cout << ans << nl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("spainting.in", "r", stdin);
// freopen("spainting.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << ' ';
ma1n();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15100 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15100 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
