Submission #768220

#TimeUsernameProblemLanguageResultExecution timeMemory
768220AugustynLogičari (COCI21_logicari)C++17
110 / 110
40 ms15680 KiB
#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); 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(dp[i].nieb_widz<inf) sum.nieb_widz=min(sum.nieb_nwidz,dp[i].nieb_widz-dp[i].bial_widz); // if(dp[i].nieb_nwidz<inf) 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 (stderr)

Main.cpp: In function 'void liczod(int, std::vector<dodp>&)':
Main.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=zacz_odteg;i<pkty_nokr.size();++i)
      |                          ~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...