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;
typedef long long ll;
#define endl '\n'
const int N = 1e5 + 5;
int dp[N][2][2][3][3];
bool vis[N];
vector<int> adj[N];
int sp = -1;
int parsp = 0;
void dfs(int node,int par){
vis[node] = 1;
for(auto ch : adj[node]){
if(ch == par) continue;
if(vis[ch]){
if(sp == -1) sp = node;
else parsp = node;
continue;
}
dfs(ch,node);
}
}
int solve(int node,int par,int cnode,int cpar,int csp,int csppar){
int &ret = dp[node][cnode][cpar][csp][csppar];
if(~ret) return ret;
if(node == sp){
if(cpar && csppar) return ret = 1e9;
if(cpar || csppar){
ret = 0;
for(auto ch : adj[node]){
if(ch == par || ch == parsp) continue;
ret += solve(ch,node,0,cnode,csp,csppar);
}
return ret;
}
else {
ret = 0;
int mn = 1e9;
for(auto ch : adj[node]){
if(ch == par || ch == parsp) continue;
ret += solve(ch,node,0,cnode,csp,csppar);
mn = min(mn , solve(ch,node,1,cnode,csp,csppar) + 1 - solve(ch,node,0,cnode,csp,csppar));
}
ret += mn;
return ret;
}
}
else {
ret = 1e9;
bool b = 0;
for(auto ch : adj[node]){
if(ch == par) continue;
if(ch == sp) b = 1;
}
if(b){
if(csp == 2){
if(cpar){
ret = 0;
for(auto ch : adj[node]){
if(ch == sp || ch == par) continue;
ret += solve(ch,node,0,cnode,0,cnode);
}
return ret;
}
else {
int c1 = 1;
for(auto ch : adj[node]){
if(ch == sp || ch == par) continue;
c1 += solve(ch,node,0,cnode,1,cnode);
}
int mn = 1e9;
ret = 0;
for(auto ch : adj[node]){
if(ch == par || ch == sp) continue;
mn = min(mn , solve(ch,node,1,cnode,0,cnode)+1 - solve(ch,node,0,cnode,0,cnode));
ret += solve(ch,node,0,cnode,0,cnode);
}
ret += mn;
ret = min(ret , c1);
return ret;
}
}
else {
if(csp && cpar) return ret = 1e9;
if(csp){
ret = 0;
for(auto ch : adj[node]){
if(ch == par) continue;
ret += solve(ch,node,(ch==sp?csp:0),cnode,csp,csppar);
}
return ret;
}
else {
int mn = 1e9;
ret = 0;
for(auto ch : adj[node]){
if(ch == par) continue;
if(ch == sp) ret += solve(ch,node,csp,cnode,csp,csppar);
else {
ret += solve(ch,node,0,cnode,csp,csppar);
mn = min(mn , solve(ch,node,1,cnode,csp,csppar)+1 - solve(ch,node,0,cnode,csp,csppar));
}
}
if(!cpar) ret += mn;
return ret;
}
}
}
else {
if(cpar){
ret = 0;
for(auto ch : adj[node]){
if(ch == par) continue;
ret += solve(ch,node,0,cnode,csp,csppar);
}
return ret;
}
else {
int mn = 1e9;
ret = 0;
for(auto ch : adj[node]){
if(ch == par) continue;
mn = min(mn , solve(ch,node,1,cnode,csp,csppar)+1 - solve(ch,node,0,cnode,csp,csppar));
ret += solve(ch,node,0,cnode,csp,csppar);
}
ret += mn;
return ret;
}
}
}
}
void solve(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,0);
memset(dp,-1,sizeof(dp));
int ans = min(solve(1,0,0,0,2,2),solve(1,0,1,0,2,2)+1);
if(ans >= 1e9) cout<<-1<<endl;
else cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
# | 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... |