Submission #379142

#	Time	Username	Problem	Language	Result	Execution time	Memory
379142		kartel	Svjetlo (COCI20_svjetlo)	C++14	30 / 110	515 ms	59520 KiB

svjetlo

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 5e5 + 500;

vector <int> g[N];
int f[N][2][2];
int a[N];

int n;

void dfs(int v, int pr) {
    int cur = 0;

    bool parity = (a[v] == 0);

    for (auto u : g[v]) {
        if (u == pr) {
            continue;
        }

        dfs(u, v);

        if (f[u][0][0] != 1e9) {
            cur += f[u][0][0] + (f[u][0][0] == 0 ? 0 : 3);
        }
        else {
            cur += f[u][0][1] + 1;
            parity = !parity;
        }
    }

    if (cur || !a[v]) {
        cur++;
    }

    f[v][0][parity] = cur;
}

int calc(int v, int pr, int sum, bool par) {
    int ret = 1e9, sumv;

    bool parity = 0;

    if (f[v][0][0] == 1e9) {
        parity = 1;
    }

    sumv = f[v][0][parity];

    for (auto u : g[v]) {
        if (u == pr) {
            continue;
        }

        int new_sumv = sumv;
        bool new_parity = parity;

        if (f[u][0][0] != 1e9) {
            new_sumv -= f[u][0][0] + (f[u][0][0] == 0 ? 0 : 3);
        }
        else {
            new_sumv -= f[u][0][1] + 1;
            new_parity = !new_parity;
        }

        ///if take one extra turn
        if (!new_parity && new_sumv == 1) {
            new_sumv = 0;
        }

        int new_sum = new_sumv;

        if (!new_sum && sum) {
            new_sum = 1;
        }

        new_sum += sum;

        if (par) {
            new_sum++;
        }
        else if (sum) {
            new_sum += 3;
        }

        /// if primary path in subtree of vertex u
        ret = min(ret, calc(u, v, new_sum, new_parity ^ par));

        if (!new_parity) {
            /// if didn't change parity
            if (!new_sumv) {
                new_sumv++;
            }

            f[v][1][0] = min(f[v][1][0], new_sumv + f[u][1][1]);
            f[v][1][1] = min(f[v][1][1], new_sumv + f[u][1][0] + 2);
        }
        else {
            f[v][1][0] = min(f[v][1][0], new_sumv + f[u][1][0] + 2);
            f[v][1][1] = min(f[v][1][1], new_sumv + f[u][1][1]);
        }
    }
    int mn[2]; mn[0] = mn[1] = 1e9;
    f[v][1][parity] = min(f[v][1][parity], max(1, f[v][0][parity]));

    /// if we haven't primary path in upper subtree and primary path go from vertex v to some vertex in subtree
    if (!sum) {
        ///good upper subtree
        ret = min(ret, f[v][1][1]);
    }
    else {
        if (par) {
            /// go down from upper subtree and change parity in vertex v
            ret = min(ret, f[v][1][0] + sum + 1);
        }
        else {
            ///need change parity in parent
            ret = min(ret, f[v][1][1] + sum + 3);
        }
    }

    bool parity_now = (f[v][0][1] != 1e9) ? 1 : 0;
    int sum_now = max(1, f[v][0][parity]);

    sum_now += sum;

    if (par) {
        parity_now = !parity_now;
        sum_now++;
    }
    else if (sum) {
        sum_now += 3;
    }

    /// two children include in primary path

    for (auto u : g[v]) {
        if (u == pr){
            continue;
        }

        bool c_parity = (f[u][0][1] != 1e9) ? 1 : 0;
        int fu = f[u][0][c_parity];

        if (c_parity) {
            fu++;
        }
        else {
            if (fu) {
                fu += 3;
            }
        }

        int new_sum = sum_now - fu;
        bool new_parity = c_parity ^ parity_now;

        /// change parity in child
        ret = min(ret, f[u][1][0] + 2 + new_sum + mn[new_parity]);
        /// without changing
        ret = min(ret, f[u][1][1] + new_sum + mn[!new_parity]);

        if (!c_parity) {
            mn[0] = min(mn[0], f[u][1][1] - fu);
            mn[1] = min(mn[1], f[u][1][0] + 2 - fu);
        }
        else {
            mn[0] = min(mn[0], f[u][1][0] + 2 - fu);
            mn[1] = min(mn[1], f[u][1][1] - fu);
        }
    }

    return ret;
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n;

    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;

        a[i] = c - '0';
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[u].pb(v);
        g[v].pb(u);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                f[i][j][k] = 1e9;
            }
        }
    }

    // calc if subtree will be good
    dfs(1, -1);

    cout << calc(1, -1, 0, 0) << el;
}


/*

7
4 6 7 2 3 1 5
*/

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