Submission #531065

#	Time	Username	Problem	Language	Result	Execution time	Memory
531065		oneloveforever	Svjetlo (COCI20_svjetlo)	C++14	30 / 110	375 ms	89080 KiB

svjetlo

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=5e5+7;
const int inf=1e9+7;
int color[M],dp[M][3][3],pre[3][3],num_child[M];
vector<vector<int> >a;
int n;
bool minimize(int &a,int b)
{
    if(a>b)
    {
        a=b;
        return true;
    }
    return false;
}
void dfs(int x,int cha)
{
    num_child[x]=(!color[x]);
    for(int node:a[x])
    {
        if(node==cha)continue;
        dfs(node,x);
        num_child[x]+=num_child[node];
    }
    if(!num_child[x])return ;
    dp[x][1-color[x]][0]=1;
    dp[x][1-color[x]][1]=1;
    dp[x][1-color[x]][2]=1;
    for(int node:a[x])
    {
        if(node==cha||!num_child[node])continue;
        for(int new_color=0;new_color<=1;new_color++)
        {
            for(int type=0;type<=2;type++)pre[new_color][type]=inf;
        }
        for(int new_color=0;new_color<=1;new_color++)
        {
            minimize(pre[new_color][0],dp[x][1-new_color][0]+dp[node][1][0]+1);
            minimize(pre[new_color][0],dp[x][new_color][0]+dp[node][0][0]+3);
            minimize(pre[new_color][1],dp[x][1-new_color][1]+dp[node][1][0]+1);
            minimize(pre[new_color][1],dp[x][new_color][1]+dp[node][1][0]+3);
            minimize(pre[new_color][1],dp[x][new_color][0]+dp[node][1][1]);
            minimize(pre[new_color][1],dp[x][1-new_color][0]+dp[node][0][1]+2);
            minimize(pre[new_color][2],dp[x][new_color][1]+dp[node][1][1]);
            minimize(pre[new_color][2],dp[x][1-new_color][1]+dp[node][0][1]+2);
            minimize(pre[new_color][2],dp[x][new_color][0]+dp[node][0][2]+1);
            minimize(pre[new_color][2],dp[x][1-new_color][0]+dp[node][1][2]+3);
            minimize(pre[new_color][2],dp[x][1-new_color][2]+dp[node][1][0]+1);
            minimize(pre[new_color][2],dp[x][new_color][2]+dp[node][0][0]+3);

        }
        for(int new_color=0;new_color<=1;new_color++)
        {
            for(int type=1;type<=2;type++)pre[new_color][type]=min(pre[new_color][type],pre[new_color][type-1]);
        }
        for(int new_color=0;new_color<=1;new_color++)
        {
            for(int type=0;type<=2;type++)dp[x][new_color][type]=pre[new_color][type];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    string s;
    cin>>s;
    a.resize(n+7);
    for(int i=1;i<=n;i++)color[i]=s[i-1]-'0';
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int node=1;node<=n;node++)
    {
        for(int new_color=0;new_color<=1;new_color++)
        {
            for(int type=0;type<=2;type++)dp[node][new_color][type]=inf;
        }
    }
    int start_node=1;
    while(color[start_node])start_node++;

    dfs(start_node,0);
    cout<<dp[start_node][1][2];
}

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