oj.uz

Submission #870890

# Submission time Handle Problem Language Result Execution time Memory
870890 2023-11-09T11:55:41 Z Rafi22 Svjetlo (COCI20_svjetlo) C++14
20 / 110
 2000 ms 86132 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 16068 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 86132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 40144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 16068 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Execution timed out 2070 ms 86132 KB Time limit exceeded
11 Halted 0 ms 0 KB -