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 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;
int dp[N][2][2][2][2];
vector < vector < int >> adj;
pair < int , int > extra = {-1, -1};
struct DSU {
vector < int > par, sz;
void init(int n) {
par = sz = vector < int > (n + 1);
for(int i = 1 ; i <= n ; i++) {
par[i] = i, sz[i] = 1;
}
}
int find(int node) {
if(par[node] == node) return node;
return par[node] = find(par[node]);
}
int join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return 0;
if(sz[v] > sz[u]) {
swap(u, v);
}
sz[u] += sz[v];
par[v] = u;
return 1;
}
};
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 ret = 1e9;
return ret = ans - mx;
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
cin >> n;
DSU s; s.init(n);
adj = vector < vector < int >> (n + 1);
for(int i = 0 ; i < n ; i++) {
int u, v;
cin >> u >> v;
if(!s.join(u, v)) {
extra = {u, v};
}
adj[u].push_back(v);
adj[v].push_back(u);
}
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 > 1e7) ans = -1;
cout << ans << endl;
return 0 ;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:113: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]
113 | for(int i = 0 ; i < adj[extra.first].size() ; i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:120: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]
120 | for(int i = 0 ; i < adj[extra.second].size() ; i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |