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(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) ((int)(x).size())
constexpr int N = 1e5 + 5;
constexpr int INF = 1e9;
int dp[N][2][2][2][2];
vector<int> v[N];
int par[N];
int u,w;
int find(int a){
if(par[a]==a) return a;
return par[a]=find(par[a]);
}
bool unite(int a,int b){
a=find(a),b=find(b);
if(a==b) return 0;
par[a]=b;
return 1;
}
int dfs(int c,int p,int fl1,int fl2,int rt,int sp){
if(c==u && fl1!=rt) return INF;
if(c==w && fl1!=sp) return INF;
if(c==w && fl2 && rt) return INF;
if(dp[c][fl1][fl2][rt][sp]!=-1) return dp[c][fl1][fl2][rt][sp];
int hm = fl2 + (c==u && sp) + (c==w && rt);
if(hm>=2) return INF;
int cur = 0;
for(int x:v[c]){
if(x==p) continue;
cur+=dfs(x,c,0,fl1,rt,sp);
}
if(hm==1){
return dp[c][fl1][fl2][rt][sp]=cur+fl1;
}
else{
int lol = INF;
for(int x:v[c]){
if(x==p) continue;
int xd = cur - dfs(x,c,0,fl1,rt,sp);
xd+=dfs(x,c,1,fl1,rt,sp);
lol=min(lol,xd);
}
return dp[c][fl1][fl2][rt][sp]=lol+fl1;
}
}
void solve(){
int n;
cin >> n;
memset(dp,-1,sizeof(dp));
iota(par,par+N,0LL);
for(int i=1;i<=n;i++){
int a,b;
cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
if(!unite(a,b)){
u=a;
w=b;
}
}
for(int i=0;i<sz(v[u]);i++){
if(v[u][i]==w) v[u].erase(v[u].begin()+i);
}
for(int i=0;i<sz(v[w]);i++){
if(v[w][i]==u) v[w].erase(v[w].begin()+i);
}
int ans = INF;
ans=min(ans,dfs(u,u,1,0,1,0));
ans=min(ans,dfs(u,u,1,0,1,1));
ans=min(ans,dfs(u,u,0,0,0,0));
ans=min(ans,dfs(u,u,0,0,0,1));
if(ans>n) cout << -1 << endl;
else cout << ans << endl;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;//cin >> t;
while(t--) solve();
}
# | 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... |