oj.uz

Submission #531065

# Submission time Handle Problem Language Result Execution time Memory
531065 2022-02-27T14:50:15 Z oneloveforever Svjetlo (COCI20_svjetlo) C++14
30 / 110
 375 ms 89080 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 53432 KB Output is correct
2 Correct 375 ms 86172 KB Output is correct
3 Correct 340 ms 89080 KB Output is correct
4 Correct 305 ms 67232 KB Output is correct
5 Correct 324 ms 77764 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 38652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -