Submission #379261

#	Time	Username	Problem	Language	Result	Execution time	Memory
379261		VEGAnn	Svjetlo (COCI20_svjetlo)	C++14	110 / 110	433 ms	84736 KiB

svjetlo

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 500100;
const int oo = 1e9; /// (!!!)
vector<int> g[N];
string s;
int n, sub[N], f[N][2][3], root;
int nf[2][3];
bool tp[N];


void amin(int &x, int y){
    x = min(x, y);
}

void dfs(int v, int p){
    sub[v] = bool(s[v] == '0');

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);

        sub[v] += sub[u];
    }

    if (sub[v] == 0) return;

    if (sub[v] == 1 && !tp[v]){
        f[v][tp[v] ^ 1][0] = 1;

        return;
    }

    f[v][tp[v] ^ 1][0] = 1;

    for (int u : g[v]){
        if (u == p) continue;

        if (sub[u] == 0) continue;

        for (int cl = 0; cl < 2; cl++)
        for (int ti = 0; ti < 3; ti++)
            nf[cl][ti] = oo;

        {
            /// ti == 0

            for (int cl = 0; cl < 2; cl++){
                amin(nf[cl ^ 1][0], f[v][cl][0] + f[u][1][0] + 1);
                amin(nf[cl][0], f[v][cl][0] + f[u][0][0] + 3);
            }
        }

        {
            /// ti == 1

            for (int cl = 0; cl < 2; cl++){
                amin(nf[cl ^ 1][1], f[v][cl][1] + f[u][1][0] + 1);
                amin(nf[cl][1], f[v][cl][1] + f[u][0][0] + 3);

                amin(nf[cl][1], f[v][cl][0] + min(f[u][1][1], f[u][1][0]));
                amin(nf[cl ^ 1][1], f[v][cl][0] + min(f[u][0][1], f[u][0][0]) + 2);
            }
        }

        {
            /// ti == 2

            for (int cl = 0; cl < 2; cl++){
                amin(nf[cl ^ 1][2], f[v][cl][0] + min(f[u][1][2], min(f[u][1][1], f[u][1][0])) + 3);
                amin(nf[cl][2], f[v][cl][0] + min(f[u][0][2], min(f[u][0][1], f[u][0][0])) + 1);

                amin(nf[cl][2], f[v][cl][1] + min(f[u][1][1], f[u][1][0]));
                amin(nf[cl ^ 1][2], f[v][cl][1] + min(f[u][0][1], f[u][0][0]) + 2);

                amin(nf[cl ^ 1][2], f[v][cl][2] + f[u][1][0] + 1);
                amin(nf[cl][2], f[v][cl][2] + f[u][0][0] + 3);
            }
        }

        for (int cl = 0; cl < 2; cl++)
        for (int ti = 0; ti < 3; ti++)
            f[v][cl][ti] = nf[cl][ti];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> s;

    for (int i = 0; i < n; i++){
        tp[i] = (s[i] - '0');
    }

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y; x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
    for (int z = 0; z < 3; z++)
        f[i][j][z] = oo;
    root = 0;

    while (root < n && tp[root]) root++;

    if (root == n){
        cout << 0;
        return 0;
    }

    dfs(root, -1);

    int ans = oo;

    for (int ti = 0; ti < 3; ti++)
        amin(ans, f[root][1][ti]);

    cout << ans;

    return 0;
}

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