Submission #379145

#	Time	Username	Problem	Language	Result	Execution time	Memory
379145		kartel	Svjetlo (COCI20_svjetlo)	C++14	110 / 110	503 ms	96108 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] == 0) {
        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 + 1] = 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);

//    for (int i = 1; i <= n; i++) {
//        for (int j = 0; j < 2; j++) {
//            cout << i << " " << j << " " << f[i][0][j] << el;
//        }
//    }

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


/*

1 0 1000000000
1 1 209
2 0 113
2 1 1000000000
3 0 71
3 1 1000000000
4 0 1000000000
4 1 21
5 0 3
5 1 1000000000
6 0 79
6 1 1000000000
7 0 1000000000
7 1 71
8 0 1000000000
8 1 55
9 0 1000000000
9 1 13
10 0 1000000000
10 1 1
11 0 39
11 1 1000000000
12 0 1000000000
12 1 7
13 0 5
13 1 1000000000
14 0 17
14 1 1000000000
15 0 1000000000
15 1 11
16 0 51
16 1 1000000000
17 0 1000000000
17 1 15
18 0 1000000000
18 1 5
19 0 1000000000
19 1 1
20 0 25
20 1 1000000000
21 0 3
21 1 1000000000
22 0 1000000000
22 1 11
23 0 1000000000
23 1 13
24 0 3
24 1 1000000000
25 0 1000000000
25 1 1
26 0 21
26 1 1000000000
27 0 1000000000
27 1 19
28 0 3
28 1 1000000000
29 0 1000000000
29 1 5
30 0 1000000000
30 1 3
31 0 1000000000
31 1 1
32 0 1000000000
32 1 1
33 0 1000000000
33 1 1
34 0 3
34 1 1000000000
35 0 1000000000
35 1 1
36 0 1000000000
36 1 1
37 0 3
37 1 1000000000
38 0 1000000000
38 1 1
39 0 7
39 1 1000000000
40 0 1000000000
40 1 1
41 0 0
41 1 1000000000
42 0 3
42 1 1000000000
43 0 3
43 1 1000000000
44 0 3
44 1 1000000000
45 0 1000000000
45 1 1
46 0 3
46 1 1000000000
47 0 1000000000
47 1 1
48 0 1000000000
48 1 1
49 0 3
49 1 1000000000
50 0 9
50 1 1000000000
51 0 1000000000
51 1 1
52 0 1000000000
52 1 1
53 0 0
53 1 1000000000
54 0 1000000000
54 1 1
55 0 1000000000
55 1 1
56 0 1000000000
56 1 1
57 0 1000000000
57 1 1
58 0 1000000000
58 1 1
59 0 1000000000
59 1 1
60 0 1000000000
60 1 7
61 0 1000000000
61 1 1
62 0 1000000000
62 1 1
63 0 1000000000
63 1 1
64 0 1000000000
64 1 1
65 0 1000000000
65 1 1
66 0 3
66 1 1000000000
67 0 0
67 1 1000000000
68 0 1000000000
68 1 1
69 0 1000000000
69 1 1
70 0 1000000000
70 1 1
71 0 1000000000
71 1 1
72 0 1000000000
72 1 1
73 0 0
73 1 1000000000
74 0 1000000000
74 1 3
75 0 1000000000
75 1 1
76 0 1000000000
76 1 1
77 0 1000000000
77 1 1
78 0 1000000000
78 1 1
79 0 1000000000
79 1 1
80 0 1000000000
80 1 1
81 0 1000000000
81 1 1
82 0 3
82 1 1000000000
83 0 1000000000
83 1 1
84 0 1000000000
84 1 1
85 0 1000000000
85 1 1
*/

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