oj.uz

Submission #379145

# Submission time Handle Problem Language Result Execution time Memory
379145 2021-03-17T10:38:21 Z kartel Svjetlo (COCI20_svjetlo) C++14
110 / 110
 503 ms 96108 KB 
#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.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 56300 KB Output is correct
2 Correct 503 ms 85672 KB Output is correct
3 Correct 482 ms 96108 KB Output is correct
4 Correct 430 ms 67180 KB Output is correct
5 Correct 482 ms 77164 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 32048 KB Output is correct
2 Correct 490 ms 36844 KB Output is correct
3 Correct 441 ms 37356 KB Output is correct
4 Correct 372 ms 33388 KB Output is correct
5 Correct 377 ms 36972 KB Output is correct
6 Correct 326 ms 34412 KB Output is correct
7 Correct 366 ms 37596 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 9 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12140 KB Output is correct
10 Correct 321 ms 56300 KB Output is correct
11 Correct 503 ms 85672 KB Output is correct
12 Correct 482 ms 96108 KB Output is correct
13 Correct 430 ms 67180 KB Output is correct
14 Correct 482 ms 77164 KB Output is correct
15 Correct 390 ms 32048 KB Output is correct
16 Correct 490 ms 36844 KB Output is correct
17 Correct 441 ms 37356 KB Output is correct
18 Correct 372 ms 33388 KB Output is correct
19 Correct 377 ms 36972 KB Output is correct
20 Correct 326 ms 34412 KB Output is correct
21 Correct 366 ms 37596 KB Output is correct
22 Correct 439 ms 39920 KB Output is correct
23 Correct 492 ms 41736 KB Output is correct
24 Correct 489 ms 40328 KB Output is correct
25 Correct 396 ms 39276 KB Output is correct
26 Correct 378 ms 45420 KB Output is correct
27 Correct 410 ms 45232 KB Output is correct
28 Correct 341 ms 40812 KB Output is correct
29 Correct 371 ms 43888 KB Output is correct
30 Correct 352 ms 41692 KB Output is correct