#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long dp[100001][2][2];
bool ss = 0;
vector<int> cyc;stack<int> st;int be[100001];
vector<int> adj[100001];
bool lol[100001];
void getcyc(int i,int pr){
if(be[i]){
cyc.push_back(i);
lol[i] = 1;
while(st.top()!=i){
cyc.push_back(st.top());
lol[st.top()] = 1;
st.pop();
}
ss = 1;return ;
}
be[i] = 1;st.push(i);
for(auto j:adj[i]){
if(j!=pr)getcyc(j,i);
if(ss)return ;
}
be[i] = 0;st.pop();
}
int solve(int i,int pr,int par,int sh){
if(dp[i][par][sh]!=-1)return dp[i][par][sh];
if(par==1){
if(sh==1){
long long c1 = 0;
for(auto j:adj[i]){
if(lol[j]||j==pr)continue;
c1+=solve(j,i,1,0);
}
return dp[i][par][sh] = c1+sh;
}else{
long long c1 = 0;
for(auto j:adj[i]){
if(lol[j]||j==pr)continue;
c1+=solve(j,i,0,0);
}
return dp[i][par][sh] = c1+sh;
}
}else{
if(sh==1){
long long c1 = 0;
for(auto j:adj[i]){
if(lol[j]||j==pr)continue;
c1+=solve(j,i,1,0);
}
long long ans = 1e9;
for(auto j:adj[i]){
if(lol[j]||j==pr)continue;
ans = min(ans,c1-solve(j,i,1,0)+solve(j,i,1,1));
}
return dp[i][par][sh] = ans+sh;
}else{
long long c1 = 0;
for(auto j:adj[i]){
if(lol[j]||j==pr)continue;
c1+=solve(j,i,0,0);
}
long long ans = 1e9;
for(auto j:adj[i]){
if(lol[j]||j==pr)continue;
ans = min(ans,c1-solve(j,i,0,0)+solve(j,i,0,1));
}
return dp[i][par][sh] = ans+sh;
}
}
}
long long dp2[100001][2][2][2][2];
int solve2(int i,int la,int sh,int fi,int shla){
if(i==0){
int c1 = min(1000000000,solve2(i+1,0,0,0,1)+solve(cyc[i],0,1,0));
c1 = min(c1,solve2(i+1,0,1,0,0)+solve(cyc[i],0,1,0));
c1 = min(c1,solve2(i+1,0,0,0,0)+solve(cyc[i],0,0,0));
c1 = min(c1,solve2(i+1,1,0,1,1)+solve(cyc[i],0,1,1));
c1 = min(c1,solve2(i+1,1,1,1,0)+solve(cyc[i],0,1,1));
c1 = min(c1,solve2(i+1,1,0,1,0)+solve(cyc[i],0,0,1));
return dp2[i][la][sh][fi][shla] = c1;
}else if(i<cyc.size()-1){
int c1 = 1e9;
if(la==0){
if(sh==0){
c1 = solve(cyc[i],0,0,0)+solve2(i+1,0,0,fi,shla);
c1 = min(c1,solve(cyc[i],0,1,0)+solve2(i+1,0,1,fi,shla));
return dp2[i][la][sh][fi][shla] = c1;
}else{
c1 = solve(cyc[i],0,0,1)+solve2(i+1,1,0,fi,shla);
c1 = min(c1,solve(cyc[i],0,1,1)+solve2(i+1,1,1,fi,shla));
return dp2[i][la][sh][fi][shla] = c1;
}
}else{
if(sh==0){
c1 = solve(cyc[i],0,1,0)+solve2(i+1,0,0,fi,shla);
return dp2[i][la][sh][fi][shla] = c1;
}else{
c1 = solve(cyc[i],0,1,1)+solve2(i+1,1,0,fi,shla);
return dp2[i][la][sh][fi][shla] = c1;
}
}
}else{
if(sh!=shla||(fi&&la)){
return dp2[i][la][sh][fi][shla] = 1e9;
}else{
return dp2[i][la][sh][fi][shla] = solve(cyc[i],0,(fi||la),sh);
}
}
}
int main(){
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);
}
getcyc(1,0);
memset(dp,-1,sizeof dp);
memset(dp2,-1,sizeof dp2);
cout<<(solve2(0,0,0,0,0)>=1e9?-1:solve2(0,0,0,0,0))<<endl;
return 0;
}
Compilation message
Main.cpp: In function 'int solve2(int, int, int, int, int)':
Main.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | }else if(i<cyc.size()-1){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18776 KB |
Output is correct |
| 2 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 3 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 5 |
Execution timed out |
1093 ms |
31716 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18776 KB |
Output is correct |
| 2 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 3 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 5 |
Execution timed out |
1093 ms |
31716 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
