#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] = min(c1+sh,1000000000ll);
}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] = min(c1+sh,1000000000ll);
}
}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(dp2[i][la][sh][fi][shla]!=-1)return dp2[i][la][sh][fi][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 = min(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 = min(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 = min(c1,solve(cyc[i],0,1,0)+solve2(i+1,0,0,fi,shla));
return dp2[i][la][sh][fi][shla] = c1;
}else{
c1 = min(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:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | }else if(i<cyc.size()-1){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18780 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 |
Correct |
112 ms |
33876 KB |
Output is correct |
6 |
Correct |
107 ms |
34920 KB |
Output is correct |
7 |
Correct |
119 ms |
34908 KB |
Output is correct |
8 |
Correct |
119 ms |
35076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18776 KB |
Output is correct |
2 |
Correct |
3 ms |
18880 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
3 ms |
18780 KB |
Output is correct |
7 |
Correct |
3 ms |
18780 KB |
Output is correct |
8 |
Correct |
3 ms |
18908 KB |
Output is correct |
9 |
Correct |
3 ms |
18776 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18884 KB |
Output is correct |
12 |
Correct |
3 ms |
18872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18776 KB |
Output is correct |
2 |
Correct |
3 ms |
18880 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
3 ms |
18780 KB |
Output is correct |
7 |
Correct |
3 ms |
18780 KB |
Output is correct |
8 |
Correct |
3 ms |
18908 KB |
Output is correct |
9 |
Correct |
3 ms |
18776 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18884 KB |
Output is correct |
12 |
Correct |
3 ms |
18872 KB |
Output is correct |
13 |
Correct |
4 ms |
18776 KB |
Output is correct |
14 |
Correct |
3 ms |
18780 KB |
Output is correct |
15 |
Correct |
4 ms |
18880 KB |
Output is correct |
16 |
Correct |
4 ms |
18780 KB |
Output is correct |
17 |
Correct |
3 ms |
18780 KB |
Output is correct |
18 |
Correct |
4 ms |
18780 KB |
Output is correct |
19 |
Correct |
4 ms |
18780 KB |
Output is correct |
20 |
Correct |
4 ms |
18780 KB |
Output is correct |
21 |
Correct |
4 ms |
18984 KB |
Output is correct |
22 |
Correct |
5 ms |
18932 KB |
Output is correct |
23 |
Correct |
4 ms |
19004 KB |
Output is correct |
24 |
Correct |
4 ms |
18780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18780 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 |
Correct |
112 ms |
33876 KB |
Output is correct |
6 |
Correct |
107 ms |
34920 KB |
Output is correct |
7 |
Correct |
119 ms |
34908 KB |
Output is correct |
8 |
Correct |
119 ms |
35076 KB |
Output is correct |
9 |
Correct |
3 ms |
18776 KB |
Output is correct |
10 |
Correct |
3 ms |
18880 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
3 ms |
18780 KB |
Output is correct |
14 |
Correct |
3 ms |
18780 KB |
Output is correct |
15 |
Correct |
3 ms |
18780 KB |
Output is correct |
16 |
Correct |
3 ms |
18908 KB |
Output is correct |
17 |
Correct |
3 ms |
18776 KB |
Output is correct |
18 |
Correct |
3 ms |
18776 KB |
Output is correct |
19 |
Correct |
3 ms |
18884 KB |
Output is correct |
20 |
Correct |
3 ms |
18872 KB |
Output is correct |
21 |
Correct |
4 ms |
18776 KB |
Output is correct |
22 |
Correct |
3 ms |
18780 KB |
Output is correct |
23 |
Correct |
4 ms |
18880 KB |
Output is correct |
24 |
Correct |
4 ms |
18780 KB |
Output is correct |
25 |
Correct |
3 ms |
18780 KB |
Output is correct |
26 |
Correct |
4 ms |
18780 KB |
Output is correct |
27 |
Correct |
4 ms |
18780 KB |
Output is correct |
28 |
Correct |
4 ms |
18780 KB |
Output is correct |
29 |
Correct |
4 ms |
18984 KB |
Output is correct |
30 |
Correct |
5 ms |
18932 KB |
Output is correct |
31 |
Correct |
4 ms |
19004 KB |
Output is correct |
32 |
Correct |
4 ms |
18780 KB |
Output is correct |
33 |
Correct |
59 ms |
22612 KB |
Output is correct |
34 |
Correct |
58 ms |
22692 KB |
Output is correct |
35 |
Correct |
62 ms |
22608 KB |
Output is correct |
36 |
Correct |
57 ms |
22608 KB |
Output is correct |
37 |
Correct |
18 ms |
20076 KB |
Output is correct |
38 |
Correct |
59 ms |
22760 KB |
Output is correct |
39 |
Correct |
7 ms |
19036 KB |
Output is correct |
40 |
Correct |
56 ms |
22604 KB |
Output is correct |
41 |
Correct |
52 ms |
23500 KB |
Output is correct |
42 |
Correct |
54 ms |
23368 KB |
Output is correct |
43 |
Correct |
80 ms |
35988 KB |
Output is correct |
44 |
Correct |
86 ms |
29648 KB |
Output is correct |