Submission #870898

#	Time	Username	Problem	Language	Result	Execution time	Memory
870898		Rafi22	Svjetlo (COCI20_svjetlo)	C++14	110 / 110	1102 ms	358696 KiB

svjetlo

#include <bits/stdc++.h>

#define ll long long
#define ld double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
int mod=1000000007;
int mod1=998244353;

const int N=500007;

vector<int>G[N];
int t[N];
bool is[N];
int DP[N][2][2];

void dfs(int v,int o)
{
    t[v]=!is[v];
    for(int i=0;i<2;i++) for(int j=0;j<2;j++) DP[v][i][j]=inf;
    DP[v][is[v]^1][0]=1;
    for(auto u:G[v])
    {
        if(u==o) continue;
        dfs(u,v);
        t[v]+=t[u];
        if(t[u]==0) continue;
        vector<vector<int>>nDP(2,vector<int>(2,inf));
        for(int x=0;x<2;x++)
        {
            for(int a=0;a<2;a++)
            {
                for(int y=0;y<2;y++)
                {
                    for(int b=0;b<2;b++)
                    {
                        if(a&&b) continue;
                        int X=x,C=0;
                        if(y==0)
                        {
                            C+=2;
                            X^=1;
                        }
                        if(!b)
                        {
                            C++;
                            X^=1;
                        }
                        nDP[X][a|b]=min(nDP[X][a|b],DP[v][x][a]+DP[u][y][b]+C);
                    }
                }
            }
        }
        for(int x=0;x<2;x++) for(int a=0;a<2;a++) DP[v][x][a]=nDP[x][a];
    }
    DP[v][0][1]=min(DP[v][0][1],DP[v][0][0]);
    DP[v][1][1]=min(DP[v][1][1],DP[v][1][0]);
}

vector<int>P[N][2][2];
vector<int>S[N][2][2];
int mem[N][2][2];

int ans=inf;
void dfs1(int v,int o)
{
    ans=min(ans,DP[v][1][1]);
    //cout<<v<<" "<<DP[v][1][1]<<endl;
    //liczymy P,S;
    for(int x=0;x<2;x++) for(int a=0;a<2;a++) S[v][x][a].resize(sz(G[v])+2,inf);
    for(int x=0;x<2;x++) for(int a=0;a<2;a++) P[v][x][a].resize(sz(G[v])+2,inf);
    P[v][is[v]^1][0][0]=1;
    for(int i=1;i<=sz(G[v]);i++)
    {
        int u=G[v][i-1];
        if(t[u]==0)
        {
            for(int x=0;x<2;x++) for(int a=0;a<2;a++) P[v][x][a][i]=P[v][x][a][i-1];
        }
        else
        {
            for(int x=0; x<2; x++)
            {
                for(int a=0; a<2; a++)
                {
                    for(int y=0; y<2; y++)
                    {
                        for(int b=0; b<2; b++)
                        {
                            if(a&&b) continue;
                            int X=x,C=0;
                            if(y==0)
                            {
                                C+=2;
                                X^=1;
                            }
                            if(!b)
                            {
                                C++;
                                X^=1;
                            }
                            P[v][X][a|b][i]=min(P[v][X][a|b][i],P[v][x][a][i-1]+DP[u][y][b]+C);
                        }
                    }
                }
            }
        }
    }
    S[v][0][0][sz(G[v])+1]=0;
    for(int i=sz(G[v]);i>0;i--)
    {
        int u=G[v][i-1];
        if(t[u]==0)
        {
            for(int x=0;x<2;x++) for(int a=0;a<2;a++) S[v][x][a][i]=S[v][x][a][i+1];
        }
        else
        {
            for(int x=0; x<2; x++)
            {
                for(int a=0; a<2; a++)
                {
                    for(int y=0; y<2; y++)
                    {
                        for(int b=0; b<2; b++)
                        {
                            if(a&&b) continue;
                            int X=x,C=0;
                            if(y==0)
                            {
                                C+=2;
                                X^=1;
                            }
                            if(!b)
                            {
                                C++;
                                X^=1;
                            }
                            S[v][X][a|b][i]=min(S[v][X][a|b][i],S[v][x][a][i+1]+DP[u][y][b]+C);
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=sz(G[v]);i++)
    {
        int u=G[v][i-1];
        if(u==o) continue;
        for(int x=0;x<2;x++) for(int a=0;a<2;a++) DP[v][x][a]=inf;
        for(int x=0; x<2; x++)
        {
            for(int a=0; a<2; a++)
            {
                for(int y=0; y<2; y++)
                {
                    for(int b=0; b<2; b++)
                    {
                        if(a&&b) continue;
                        DP[v][x^y][a|b]=min(DP[v][x^y][a|b],P[v][x][a][i-1]+S[v][y][b][i+1]);
                    }
                }
            }
        }
        t[v]-=t[u];
        t[u]+=t[v];
        for(int x=0;x<2;x++) for(int a=0;a<2;a++) mem[u][x][a]=DP[u][x][a];
        if(t[v]>0)
        {
            vector<vector<int>>nDP(2,vector<int>(2,inf));
            for(int x=0; x<2; x++)
            {
                for(int a=0; a<2; a++)
                {
                    for(int y=0; y<2; y++)
                    {
                        for(int b=0; b<2; b++)
                        {
                            if(a&&b) continue;
                            int X=x,C=0;
                            if(y==0)
                            {
                                C+=2;
                                X^=1;
                            }
                            if(!b)
                            {
                                C++;
                                X^=1;
                            }
                            nDP[X][a|b]=min(nDP[X][a|b],DP[u][x][a]+DP[v][y][b]+C);
                        }
                    }
                }
            }
            for(int x=0; x<2; x++) for(int a=0; a<2; a++) DP[u][x][a]=nDP[x][a];
        }
        dfs1(u,v);
    }
    for(int x=0;x<2;x++) for(int a=0;a<2;a++) DP[v][x][a]=mem[v][x][a];
    t[v]-=t[o];
    t[o]+=t[v];
}


signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,a,b;
    string s;
    cin>>n>>s;
    for(int i=0;i<n;i++) is[i+1]=s[i]-'0';
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(1,0);
    dfs1(1,0);
    cout<<ans;


    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30