Submission #870890

#	Time	Username	Problem	Language	Result	Execution time	Memory
870890		Rafi22	Svjetlo (COCI20_svjetlo)	C++14	20 / 110	2070 ms	86132 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]);
}


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);
    }
    int ans=inf;
    for(int i=1;i<=n;i++)
    {
        dfs(i,0);
        ans=min(ans,DP[i][1][1]);
    }
    cout<<ans;


    return 0;
}

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