#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 1e5 + 5;
int n;
vector < int > tim;
int dp[N][2][2][2][2];
vector < vector < int >> adj;
pair < int , int > extra = {-1, -1};
void dfs(int node, int par) {
for(auto ch : adj[node]) {
if(ch == par) continue;
if(tim[ch] < tim[node]) {
extra = {node, ch};
} else {
tim[ch] = tim[node] + 1;
dfs(ch, node);
}
}
}
int solve(int node, int par, int color_par, int color_node, int color_extra1, int color_extra2) {
auto &ret = dp[node][color_par][color_node][color_extra1][color_extra2];
if(ret != -1) {
return ret;
}
int counter = color_par;
for(auto child : adj[node]) {
if(child == par) continue;
if(child == extra.first) {
counter += color_extra1;
} else if(child == extra.second) {
counter += color_extra2;
}
}
if(node == extra.first) counter += color_extra2;
else if(node == extra.second) counter += color_extra1;
if(counter >= 2) {
return ret = 1e9;
} else if(counter == 1) {
int ans = 0;
for(auto child : adj[node]) {
if(child == par) continue;
if(child == extra.first) {
ans += solve(child, node, color_node, color_extra1, color_extra1, color_extra2);
} else if(child == extra.second) {
ans += solve(child, node, color_node, color_extra2, color_extra1, color_extra2);
} else {
ans += solve(child, node, color_node, 0, color_extra1, color_extra2);
}
}
return ret = ans;
} else {
int ans = 0, mx = -1e16;
for(auto child : adj[node]) {
if(child == par) continue;
if(child == extra.first) {
ans += solve(child, node, color_node, color_extra1, color_extra1, color_extra2);
} else if(child == extra.second) {
ans += solve(child, node, color_node, color_extra2, color_extra1, color_extra2);
} else {
int b = solve(child, node, color_node, 1, color_extra1, color_extra2) + 1;
int a = solve(child, node, color_node, 0, color_extra1, color_extra2);
ans += a, mx = max(mx, a - b);
}
}
if(mx < -1e15) return 1e9;
return ret = ans - mx;
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
cin >> n;
tim = vector < int > (n + 1);
adj = vector < vector < int >> (n + 1);
for(int i = 0 ; i < n ; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
for(int i = 0 ; i < adj[extra.first].size() ; i++) {
if(adj[extra.first][i] == extra.second) {
adj[extra.first].erase(adj[extra.first].begin() + i);
break;
}
}
for(int i = 0 ; i < adj[extra.second].size() ; i++) {
if(adj[extra.second][i] == extra.first) {
adj[extra.second].erase(adj[extra.second].begin() + i);
break;
}
}
cerr << extra.first << " " << extra.second << endl;
int ans = 1e9;
memset(dp, -1, sizeof(dp));
if(extra.first == 1) {
int a = solve(1, 1, 0, 0, 0, 0);
int b = solve(1, 1, 0, 1, 1, 0) + 1;
int c = solve(1, 1, 0, 0, 0, 1) + 1;
int d = solve(1, 1, 0, 1, 1, 1) + 2;
ans = min({a, b, c, d});
} else if(extra.second == 1) {
int a = solve(1, 1, 0, 0, 0, 0);
int b = solve(1, 1, 0, 0, 1, 0) + 1;
int c = solve(1, 1, 0, 1, 0, 1) + 1;
int d = solve(1, 1, 0, 1, 1, 1) + 2;
ans = min({a, b, c, d});
} else {
int a = solve(1, 1, 0, 0, 0, 0);
int b = solve(1, 1, 0, 0, 1, 0) + 1;
int c = solve(1, 1, 0, 0, 0, 1) + 1;
int d = solve(1, 1, 0, 0, 1, 1) + 2;
int e = solve(1, 1, 0, 1, 0, 0) + 1;
int f = solve(1, 1, 0, 1, 1, 0) + 2;
int g = solve(1, 1, 0, 1, 0, 1) + 2;
int h = solve(1, 1, 0, 1, 1, 1) + 3;
ans = min({a, b, c, d, e, f, g, h});
}
if(ans > 1e8) ans = -1;
cout << ans << endl;
return 0 ;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0 ; i < adj[extra.first].size() ; i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 0 ; i < adj[extra.second].size() ; i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
121 ms |
34472 KB |
Output is correct |
| 6 |
Correct |
116 ms |
34476 KB |
Output is correct |
| 7 |
Correct |
115 ms |
34472 KB |
Output is correct |
| 8 |
Correct |
141 ms |
34480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
121 ms |
34472 KB |
Output is correct |
| 6 |
Correct |
116 ms |
34476 KB |
Output is correct |
| 7 |
Correct |
115 ms |
34472 KB |
Output is correct |
| 8 |
Correct |
141 ms |
34480 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
