oj.uz

Submission #768206

# Submission time Handle Problem Language Result Execution time Memory
768206 2023-06-27T17:02:45 Z Augustyn Logičari (COCI21_logicari) C++17
20 / 110
 40 ms 15700 KB 
#include<iostream>
#include<vector>
using namespace std;
#define inf 1000000
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

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);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 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 39 ms 15652 KB Output is correct
6 Correct 40 ms 15612 KB Output is correct
7 Correct 38 ms 15632 KB Output is correct
8 Correct 38 ms 15700 KB Output is correct

Subtask #2
10.0 / 10.0

# 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 40.0

# 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 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 39 ms 15652 KB Output is correct
6 Correct 40 ms 15612 KB Output is correct
7 Correct 38 ms 15632 KB Output is correct
8 Correct 38 ms 15700 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -