#include<iostream>
#include<vector>
using namespace std;
#define inf 100001
struct dodp
{
int nieb_widz,nieb_nwidz,
bial_widz,bial_nwidz;
dodp(int a, int b, int c, int d)
{
nieb_widz=a;
nieb_nwidz=b;
bial_widz=c;
bial_nwidz=d;
}
dodp()
{
}
};
vector<vector<int>>pol;
vector<bool>bylem;
vector<bool>okr;
vector<dodp>dp;
vector<int>pkty_nokr;
int szuk_okr(int ter,int popr)
{
bylem[ter]=1;
for(auto i:pol[ter])
{
if(i==popr)
continue;
if(bylem[i])
{
pkty_nokr.push_back(ter);
okr[ter]=1;
return i;
}
int dtg=szuk_okr(i,ter);
if(dtg==-1)
return -1;
else if(dtg)
{
okr[ter]=1;
pkty_nokr.push_back(ter);
if(ter==dtg)
return -1;
else
return dtg;
}
}
return 0;
}
void licz_dp(int ter,int popr)
{
dodp sum(inf,inf,0,0);
bool czy_zm_bi=0,czy_zm_nb=1;
for(auto i:pol[ter])
{
if(i==popr||okr[i])
continue;
licz_dp(i,ter);
sum.bial_nwidz+=dp[i].bial_nwidz;
sum.bial_widz+=dp[i].bial_widz;
if(czy_zm_bi==0&&dp[i].nieb_widz<inf)
{
if(dp[i].bial_widz>=inf)
{
sum.nieb_widz=dp[i].nieb_widz-dp[i].bial_widz;
czy_zm_bi=1;
}
else
sum.nieb_widz=min(sum.nieb_nwidz,dp[i].nieb_widz-dp[i].bial_widz);
}
if(czy_zm_nb==0&&dp[i].nieb_nwidz<inf)
{
if(dp[i].bial_nwidz>=inf)
{
sum.nieb_nwidz=dp[i].nieb_nwidz-dp[i].bial_nwidz;
czy_zm_nb=1;
}
else
sum.nieb_nwidz=min(sum.nieb_nwidz,dp[i].nieb_nwidz-dp[i].bial_nwidz);
}
}
dp[ter].bial_nwidz=sum.bial_widz;
dp[ter].nieb_nwidz=sum.bial_nwidz+1;
dp[ter].bial_widz=sum.bial_widz+sum.nieb_widz;
dp[ter].nieb_widz=sum.bial_nwidz+sum.nieb_nwidz+1;
}
void liczod(int zacz_odteg,vector<dodp>&dp2)
{
for(int i=zacz_odteg;i<pkty_nokr.size();++i)
{
dp2[i].bial_nwidz=dp2[i-1].bial_widz+dp[pkty_nokr[i]].bial_nwidz;
dp2[i].nieb_nwidz=dp2[i-1].bial_nwidz+dp[pkty_nokr[i]].nieb_nwidz;
dp2[i].bial_widz=min(dp2[i-1].bial_widz+dp[pkty_nokr[i]].bial_widz,
dp2[i-1].nieb_widz+dp[pkty_nokr[i]].bial_nwidz);
dp2[i].nieb_widz=min(dp2[i-1].bial_nwidz+dp[pkty_nokr[i]].nieb_widz,
dp2[i-1].nieb_nwidz+dp[pkty_nokr[i]].nieb_nwidz);
}
}
int main()
{
int n;
scanf("%d",&n);
pol.resize(n+1);
bylem.resize(n+1,0);
okr.resize(n+1,0);
dp.resize(n+1);
for(int i=0;i<n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
pol[a].push_back(b);
pol[b].push_back(a);
}
szuk_okr(1,0);
for(int i=1;i<=n;++i)
{
dp[i].nieb_widz=dp[i].bial_widz=
dp[i].nieb_nwidz=dp[i].bial_nwidz=inf;
if(okr[i])
{
if(pol[i].size()==2)
{
dp[i].bial_nwidz=0;
dp[i].nieb_nwidz=1;
}
}
else
{
if(pol[i].size()==1)
{
dp[i].bial_nwidz=0;
dp[i].nieb_nwidz=1;
}
}
}
for(auto i:pkty_nokr)
licz_dp(i,0);
vector<dodp>dp2(pkty_nokr.size());
dodp pom(inf,inf,inf,inf);
int odp=inf;
dp2[0]=pom;
dp2[0].bial_widz=dp[pkty_nokr[0]].bial_widz;
liczod(1,dp2);
odp=min(odp,dp2[pkty_nokr.size()-1].bial_widz);
dp2[0]=pom;
dp2[0].nieb_widz=dp[pkty_nokr[0]].nieb_widz;
liczod(1,dp2);
odp=min(odp,dp2[pkty_nokr.size()-1].bial_nwidz);
dp2[0]=pom;
dp2[1]=pom;
dp2[0].bial_nwidz=dp[pkty_nokr[0]].bial_nwidz;
dp2[1].bial_nwidz=dp2[0].bial_nwidz+dp[pkty_nokr[1]].bial_nwidz;
dp2[1].bial_widz=dp2[0].bial_nwidz+dp[pkty_nokr[1]].bial_widz;
liczod(2,dp2);
odp=min(odp,dp2[pkty_nokr.size()-1].nieb_widz);
dp2[0]=pom;
dp2[1]=pom;
dp2[0].bial_nwidz=dp[pkty_nokr[0]].bial_nwidz;
dp2[1].nieb_nwidz=dp2[0].bial_nwidz+dp[pkty_nokr[1]].nieb_nwidz;
dp2[1].nieb_widz=dp2[0].bial_nwidz+dp[pkty_nokr[1]].nieb_widz;
liczod(2,dp2);
odp=min(odp,dp2[pkty_nokr.size()-1].bial_widz);
dp2[0]=pom;
dp2[1]=pom;
dp2[0].nieb_nwidz=dp[pkty_nokr[0]].nieb_nwidz;
dp2[1].bial_widz=dp2[0].nieb_nwidz+dp[pkty_nokr[1]].bial_nwidz;
liczod(2,dp2);
odp=min(odp,dp2[pkty_nokr.size()-1].nieb_nwidz);
dp2[0]=pom;
dp2[1]=pom;
dp2[0].nieb_nwidz=dp[pkty_nokr[0]].nieb_nwidz;
dp2[1].nieb_widz=dp2[0].nieb_nwidz+dp[pkty_nokr[1]].nieb_nwidz;
liczod(2,dp2);
odp=min(odp,dp2[pkty_nokr.size()-1].bial_nwidz);
if(odp==inf)
printf("-1");
else
printf("%d",odp);
return 0;
}
Compilation message
Main.cpp: In function 'void liczod(int, std::vector<dodp>&)':
Main.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=zacz_odteg;i<pkty_nokr.size();++i)
| ~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Main.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
38 ms |
15700 KB |
Output is correct |
| 6 |
Correct |
36 ms |
15676 KB |
Output is correct |
| 7 |
Correct |
37 ms |
15688 KB |
Output is correct |
| 8 |
Correct |
41 ms |
15604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
38 ms |
15700 KB |
Output is correct |
| 6 |
Correct |
36 ms |
15676 KB |
Output is correct |
| 7 |
Correct |
37 ms |
15688 KB |
Output is correct |
| 8 |
Correct |
41 ms |
15604 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
