#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 100005;
const int INF = 1000000007;
int n, root, special;
int head[MAXN], par[MAXN];
int dp[MAXN][2][2][2][2];
vector <int> v[MAXN];
int nadi (int x) {
if (x == head[x]) return x;
return head[x] = nadi(head[x]);
}
void dfs (int x, int rod) {
par[x] = rod;
for (auto sus : v[x]) {
if (sus == rod) continue;
dfs(sus, x);
}
}
int calc (int x, int me, int up, int rt, int sp) {
if (dp[x][me][up][rt][sp] != -1) return dp[x][me][up][rt][sp];
llint res = INF;
bool ok = 1;
if (x == root && me != rt) ok = 0;
if (x == special && me != sp) ok = 0;
if (x == special && up && rt) ok = 0;
if (!ok) return dp[x][me][up][rt][sp] = INF;
bool covered = 0;
if (up) covered = 1;
if (x == root && sp) covered = 1;
if (x == special && rt) covered = 1;
llint sum = me;
for (auto sus : v[x]) {
if (sus == par[x]) continue;
sum += calc(sus, 0, me, rt, sp);
}
if (covered) {
res = min(res, sum);
} else {
for (auto sus : v[x]) {
if (sus == par[x]) continue;
llint val = sum - calc(sus, 0, me, rt, sp) + calc(sus, 1, me, rt, sp);
res = min(res, val);
}
}
return dp[x][me][up][rt][sp] = res;
}
void solve () {
int sol = INF;
for (int rt = 0; rt <= 1; rt++) {
for (int sp = 0; sp <= 1; sp++) {
sol = min(sol, calc(root, rt, 0, rt, sp));
}
}
if (sol == INF) cout << -1; else cout << sol;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
memset(dp, -1, sizeof dp);
cin >> n;
for (int i = 1; i <= n; i++) {
head[i] = i;
}
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
int pa = nadi(a);
int pb = nadi(b);
if (pa == pb) {
root = a;
special = b;
} else {
head[pa] = pb;
v[a].push_back(b);
v[b].push_back(a);
}
}
dfs(root, 0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8908 KB |
Output is correct |
2 |
Correct |
3 ms |
8908 KB |
Output is correct |
3 |
Correct |
3 ms |
8908 KB |
Output is correct |
4 |
Correct |
4 ms |
8908 KB |
Output is correct |
5 |
Correct |
162 ms |
26900 KB |
Output is correct |
6 |
Correct |
186 ms |
26904 KB |
Output is correct |
7 |
Correct |
198 ms |
26924 KB |
Output is correct |
8 |
Correct |
160 ms |
26908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8908 KB |
Output is correct |
2 |
Correct |
3 ms |
8908 KB |
Output is correct |
3 |
Correct |
3 ms |
8908 KB |
Output is correct |
4 |
Correct |
4 ms |
8908 KB |
Output is correct |
5 |
Correct |
6 ms |
8892 KB |
Output is correct |
6 |
Correct |
5 ms |
8908 KB |
Output is correct |
7 |
Correct |
5 ms |
8908 KB |
Output is correct |
8 |
Correct |
4 ms |
8908 KB |
Output is correct |
9 |
Correct |
6 ms |
8908 KB |
Output is correct |
10 |
Correct |
4 ms |
8908 KB |
Output is correct |
11 |
Correct |
4 ms |
8908 KB |
Output is correct |
12 |
Correct |
3 ms |
8908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8908 KB |
Output is correct |
2 |
Correct |
3 ms |
8908 KB |
Output is correct |
3 |
Correct |
3 ms |
8908 KB |
Output is correct |
4 |
Correct |
4 ms |
8908 KB |
Output is correct |
5 |
Correct |
6 ms |
8892 KB |
Output is correct |
6 |
Correct |
5 ms |
8908 KB |
Output is correct |
7 |
Correct |
5 ms |
8908 KB |
Output is correct |
8 |
Correct |
4 ms |
8908 KB |
Output is correct |
9 |
Correct |
6 ms |
8908 KB |
Output is correct |
10 |
Correct |
4 ms |
8908 KB |
Output is correct |
11 |
Correct |
4 ms |
8908 KB |
Output is correct |
12 |
Correct |
3 ms |
8908 KB |
Output is correct |
13 |
Correct |
4 ms |
8908 KB |
Output is correct |
14 |
Correct |
4 ms |
8908 KB |
Output is correct |
15 |
Correct |
4 ms |
8908 KB |
Output is correct |
16 |
Correct |
5 ms |
8908 KB |
Output is correct |
17 |
Correct |
4 ms |
8908 KB |
Output is correct |
18 |
Correct |
6 ms |
8908 KB |
Output is correct |
19 |
Correct |
4 ms |
8908 KB |
Output is correct |
20 |
Correct |
4 ms |
8908 KB |
Output is correct |
21 |
Correct |
4 ms |
8908 KB |
Output is correct |
22 |
Correct |
4 ms |
8908 KB |
Output is correct |
23 |
Correct |
5 ms |
9048 KB |
Output is correct |
24 |
Correct |
6 ms |
9036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8908 KB |
Output is correct |
2 |
Correct |
3 ms |
8908 KB |
Output is correct |
3 |
Correct |
3 ms |
8908 KB |
Output is correct |
4 |
Correct |
4 ms |
8908 KB |
Output is correct |
5 |
Correct |
162 ms |
26900 KB |
Output is correct |
6 |
Correct |
186 ms |
26904 KB |
Output is correct |
7 |
Correct |
198 ms |
26924 KB |
Output is correct |
8 |
Correct |
160 ms |
26908 KB |
Output is correct |
9 |
Correct |
3 ms |
8908 KB |
Output is correct |
10 |
Correct |
3 ms |
8908 KB |
Output is correct |
11 |
Correct |
3 ms |
8908 KB |
Output is correct |
12 |
Correct |
4 ms |
8908 KB |
Output is correct |
13 |
Correct |
6 ms |
8892 KB |
Output is correct |
14 |
Correct |
5 ms |
8908 KB |
Output is correct |
15 |
Correct |
5 ms |
8908 KB |
Output is correct |
16 |
Correct |
4 ms |
8908 KB |
Output is correct |
17 |
Correct |
6 ms |
8908 KB |
Output is correct |
18 |
Correct |
4 ms |
8908 KB |
Output is correct |
19 |
Correct |
4 ms |
8908 KB |
Output is correct |
20 |
Correct |
3 ms |
8908 KB |
Output is correct |
21 |
Correct |
4 ms |
8908 KB |
Output is correct |
22 |
Correct |
4 ms |
8908 KB |
Output is correct |
23 |
Correct |
4 ms |
8908 KB |
Output is correct |
24 |
Correct |
5 ms |
8908 KB |
Output is correct |
25 |
Correct |
4 ms |
8908 KB |
Output is correct |
26 |
Correct |
6 ms |
8908 KB |
Output is correct |
27 |
Correct |
4 ms |
8908 KB |
Output is correct |
28 |
Correct |
4 ms |
8908 KB |
Output is correct |
29 |
Correct |
4 ms |
8908 KB |
Output is correct |
30 |
Correct |
4 ms |
8908 KB |
Output is correct |
31 |
Correct |
5 ms |
9048 KB |
Output is correct |
32 |
Correct |
6 ms |
9036 KB |
Output is correct |
33 |
Correct |
109 ms |
12444 KB |
Output is correct |
34 |
Correct |
110 ms |
12432 KB |
Output is correct |
35 |
Correct |
95 ms |
12412 KB |
Output is correct |
36 |
Correct |
97 ms |
12444 KB |
Output is correct |
37 |
Correct |
23 ms |
9832 KB |
Output is correct |
38 |
Correct |
103 ms |
12632 KB |
Output is correct |
39 |
Correct |
9 ms |
9164 KB |
Output is correct |
40 |
Correct |
106 ms |
12356 KB |
Output is correct |
41 |
Correct |
60 ms |
13476 KB |
Output is correct |
42 |
Correct |
75 ms |
13192 KB |
Output is correct |
43 |
Correct |
129 ms |
26980 KB |
Output is correct |
44 |
Correct |
140 ms |
19972 KB |
Output is correct |