#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1e5+5;
int n, dp[N][2][2], dp2[N][2][2][2][2], tr[N], dp3[N][2][2];
vector<int> adj[N], cyc;
bool inc[N], ins[N], vis[N];
void get_cyc(int u, int p) {
if (!cyc.empty())return;
if (ins[u]) {
cyc.pb(u);
int cur = tr[u];
inc[u] = true;
while (cur != u) {
cyc.pb(cur);
inc[cur] = true;
cur = tr[cur];
}
return;
}
if (vis[u])return;
vis[u] = ins[u] = true;
for (auto &v : adj[u]) {
if (v == p)continue;
tr[u] = v;
get_cyc(v, u);
if (!cyc.empty())return;
}
ins[u] = false;
}
int sol2(int u, int p, int val, int pv) {
int &ret = dp[u][val][pv];
if (~ret)return ret;
ret = val;
if (!pv) {
int mn = -1e6;
int f, s;
bool fl = false, f2 = false, fx = false;
for (auto &v : adj[u]) {
if (v == p || inc[v])continue;
fx = true;
f = sol2(v, u, 0, val), s = sol2(v, u, 1, val);
if (f == s && f == int(1e6))return ret = int(1e6);
if (f == int(1e6)) {
if (fl)return ret = int(1e6);
ret += (mn == -1e6 ? 0 : mn);
mn = -1e6;
fl = true;
ret += s;
continue;
}
if (s == int(1e6)) {
ret += f;
continue;
}
if (f-s > mn) {
ret += (mn == -1e6 ? 0 : mn);
mn = f-s;
ret += s;
f2 = true;
} else {
ret += f;
}
}
if (!fx || (!fl && !f2))return ret = int(1e6);
} else {
for (auto &v : adj[u]) {
if (v == p || inc[v])continue;
ret += sol2(v, u, 0, val);
if (ret > int(1e6))return ret = int(1e6);
}
}
ret = min(ret, int(1e6));
return ret;
}
int get(int u, int x, int val) {
int &ret = dp3[u][x][val];
if (~ret)return ret;
ret = 0;
bool fx = false;
if (!x) {
int mn = -1e6;
bool fl = false, f2 = false;
for (auto &v : adj[u]) {
if (inc[v])continue;
fx = true;
int f = sol2(v, u, 0, val), s = sol2(v, u, 1, val);
if (f == s && f == int(1e6))return ret = int(1e6);
if (f == int(1e6)) {
if (fl)return ret = int(1e6);
ret += (mn == -1e6 ? 0 : mn);
mn = -1e6;
fl = true;
ret += s;
continue;
}
if (s == int(1e6)) {
ret += f;
continue;
}
if (f-s > mn) {
ret += (mn == -1e6 ? 0 : mn);
mn = f-s;
ret += s;
f2 = true;
} else {
ret += f;
}
}
if (!fx)return ret = int(1e6);
if (!fl && !f2)return ret = int(1e6);
} else {
for (auto &v : adj[u]) {
if (inc[v])continue;
ret += sol2(v, u, 0, val);
if (ret > int(1e6))return ret = int(1e6);
}
}
return ret;
}
int sol(int i, int ls, int nls, int f, int nf) {
int &ret = dp2[i][ls][nls][f][nf];
if (~ret)return ret;
if (!i) {
int c1 = get(cyc[i], 0, 0) + sol(i+1, 0, 1, 0, 1);
c1 = min({c1, int(1e6), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
int c2 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, 1, 1);
c2 = min({c2, int(1e6), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
return ret = min({int(1e6), c1, c2});
} else if (i == sz(cyc) - 1) {
if (f && ls)return ret = int(1e6);
if (nf+nls == 1)return ret = int(1e6);
if (nf + nls == 0) {
if (f + ls == 0) {
return ret = min(int(1e6), get(cyc[i], 0, 1) + 1);
} else {
return ret = min(int(1e6), 1 + get(cyc[i], 1, 1));
}
}
if (f + ls == 0)return ret = get(cyc[i], 0, 0);
return ret = get(cyc[i], 1, 0);
} else if (i == 1) {
if (ls) {
if (nf)return ret = min(int(1e6), get(cyc[i], 1, 0) + sol(i+1, 0, 1, f, nf));
int c1 = get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 1, f, 1);
int c2 = get(cyc[i], 1, 0) + sol(i+1, 0, 1, f, 0);
return ret = min({int(1e6), c1, c2});
}
if (nf)return ret = min(int(1e6), get(cyc[i], 0, 0) + sol(i+1, 0, 1, f, nf));
int c1 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, f, 1);
c1 = min(c1, get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, f, 1));
int c2 = get(cyc[i], 0, 0) + sol(i+1, 0, 1, f, 0);
c2 = min(c2, get(cyc[i], 1, 0) + sol(i+1, 0, 0, f, 0));
return ret = min({int(1e6), c1, c2});
} else {
if (!nls) {
int c1 = get(cyc[i], ls, 1)+1+sol(i+1, 1, 1, f, nf);
c1 = min(c1, get(cyc[i], 1, 1)+1+sol(i+1, 1, ls, f, nf));
return ret = min(int(1e6), c1);
}
int c1 = get(cyc[i], ls, 0)+sol(i+1, 0, 1, f, nf);
c1 = min(c1, get(cyc[i], 1, 0)+sol(i+1, 0, ls, f, nf));
return ret = min(int(1e6), c1);
}
return ret;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].pb(v);
adj[v].pb(u);
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k] = dp3[i][j][k] = -1;
for (int l = 0; l < 2; l++) {
for (int m = 0; m < 2; m++) {
dp2[i][j][k][l][m] = -1;
}
}
}
}
}
get_cyc(0, 0);
int x = sol(0, 0, 0, 0, 0);
cout << (x > n ? -1 : x) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
71 ms |
28840 KB |
Output is correct |
| 6 |
Correct |
72 ms |
28884 KB |
Output is correct |
| 7 |
Correct |
78 ms |
28876 KB |
Output is correct |
| 8 |
Correct |
70 ms |
28876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
71 ms |
28840 KB |
Output is correct |
| 6 |
Correct |
72 ms |
28884 KB |
Output is correct |
| 7 |
Correct |
78 ms |
28876 KB |
Output is correct |
| 8 |
Correct |
70 ms |
28876 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
