oj.uz

Submission #379088

# Submission time Handle Problem Language Result Execution time Memory
379088 2021-03-17T09:43:37 Z ne4eHbKa Svjetlo (COCI20_svjetlo) C++17
110 / 110
 819 ms 124588 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t i8;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
#define int ll
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

int n;
const int N = 5e5 + 5;
vector<int> g[N], h;
i8 p[N];
bool unlit[N], mk[N];
int s[2][N], t[2][N], f[2][N], e[N], T[2][2][N], S[2][3][N], rT[2][2][N];

int min(int a, int b, int c) {return min(a, min(b, c));}
int min(int a, int b, int c, int d) {return min(min(a, d), min(b, c));}

void solve() {
    cin >> n;
#ifdef KEK
    memset(mk, 0, N);
    for(int i = 0; i < n; ++i)
        g[i].clear();
#endif
    for(int i = 0; i < n; ++i) {
        char c; cin >> c;
        p[i] = c == '0';
        e[i] = 0;
    }
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
        ++e[u], ++e[v];
    }
    deque<int> q;
    for(int i = 0; i < n; ++i)
        if(e[i] == 1)
            p[i]
                ? q.push_back(i)
                : q.push_front(i);
    int cnt = 0;
    for(;;) {
        ++cnt;
        assert(!q.empty());
        int v = q.front();
        q.pop_front();
        mk[v] = true;
        unlit[v] = p[v];
        h.clear();
        for(int u : g[v]) {
            if(--e[u] == 1)
                unlit[u] || unlit[v]
                    ? q.push_back(u)
                    : q.push_front(u);
            if(mk[u] && unlit[u]) {
                unlit[v] = true;
                h.push_back(u);
            }
        }
        if(!unlit[v]) continue;
        int k = len(h);
        f[0][v] = +inf;
        f[1][v] = 1;
        for(int u : h) {
            int f0 = min(f[1][v] + f[0][u] + 1,
                         f[0][v] + f[1][u] + 3);
            int f1 = min(f[0][v] + f[0][u] + 1,
                         f[1][v] + f[1][u] + 3);
            f[0][v] = min(+inf, f0);
            f[1][v] = min(+inf, f1);
        }

        for(int i : {0, 1}) for(int j : {0, 1})
            fill(T[i][j], T[i][j] + k + 1, +inf);
        T[1][0][0] = 1;
        for(int i = 0; i < k; ++i) {
            for(int p : {0, 1}) {
                for(int z : {0, 1})
                    for(int ff : {0, 1})
                        umin(T[p ^ ff ^ 1][z][i + 1],
                             T[p][z][i] + f[ff][h[i]] + 1 + (ff << 1));
                for(int e : {0, 1})
                    umin(T[p ^ e][1][i + 1],
                         T[p][0][i] + t[e][h[i]] + (e << 1));
            }
        }

        t[0][v] = min(T[0][0][k], T[0][1][k], f[0][v]);
        t[1][v] = min(T[1][0][k], T[1][1][k], f[1][v]);
        for(int i : {0, 1}) for(int j : {0, 1, 2})
            fill(S[i][j], S[i][j] + k + 1, +inf);
        S[1][0][0] = 1;
        for(int i = 0; i < k; ++i) {
            for(int p : {0, 1}) {
                for(int z : {0, 1, 2})
                    for(int ff : {0, 1})
                        umin(S[p ^ ff ^ 1][z][i + 1],
                             S[p][z][i] + f[ff][h[i]] + 1 + (ff << 1));
                for(int z : {0, 1})
                    for(int e : {0, 1})
                        umin(S[p ^ e][z + 1][i + 1],
                            S[p][z][i] + t[e][h[i]] + (e << 1));
            }
        }
        s[0][v] = min(S[0][0][k], S[0][1][k], S[0][2][k], t[0][v]);
        s[1][v] = min(S[1][0][k], S[1][1][k], S[1][2][k], t[1][v]);

        for(int i : {0, 1}) for(int j : {0, 1})
            fill(rT[i][j], rT[i][j] + k + 1, +inf);
        rT[0][0][0] = 1;
        for(int i = 0; i < k; ++i) {
            for(int p : {0, 1}) {
                for(int z : {0, 1})
                    for(int ff : {0, 1})
                        umin(rT[p ^ ff ^ 1][z][i + 1],
                             rT[p][z][i] + f[ff][h[k - 1 - i]] + 1 + (ff << 1));
                for(int e : {0, 1})
                    umin(rT[p ^ e][1][i + 1],
                         rT[p][0][i] + t[e][h[k - 1 - i]] + (e << 1));
            }
        }

        for(int i = 0; i < k; ++i) {
            for(int fi : {0, 1}) {
                for(int se : {0, 1}) {
                    ll P = s[1][h[i]];
                    P += T[fi][0][i];
                    P += rT[se][0][k - 1 - i];
                    if(P > +inf) continue;
                    umin(s[fi ^ se][v], int(P));
                }
            }
        }
        if(p[v]) {
            swap(f[0][v], f[1][v]);
            swap(t[0][v], t[1][v]);
            swap(s[0][v], s[1][v]);
        }
        if(cnt == n) {
            cout << s[0][v] << endl;
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 40812 KB Output is correct
2 Correct 626 ms 52792 KB Output is correct
3 Correct 621 ms 51480 KB Output is correct
4 Correct 577 ms 48876 KB Output is correct
5 Correct 646 ms 53100 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 50644 KB Output is correct
2 Correct 700 ms 66300 KB Output is correct
3 Correct 819 ms 64492 KB Output is correct
4 Correct 625 ms 59912 KB Output is correct
5 Correct 624 ms 66668 KB Output is correct
6 Correct 520 ms 60908 KB Output is correct
7 Correct 726 ms 124588 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12268 KB Output is correct
2 Correct 8 ms 12268 KB Output is correct
3 Correct 8 ms 12268 KB Output is correct
4 Correct 9 ms 12268 KB Output is correct
5 Correct 8 ms 12268 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 8 ms 12268 KB Output is correct
8 Correct 8 ms 12268 KB Output is correct
9 Correct 8 ms 12288 KB Output is correct
10 Correct 437 ms 40812 KB Output is correct
11 Correct 626 ms 52792 KB Output is correct
12 Correct 621 ms 51480 KB Output is correct
13 Correct 577 ms 48876 KB Output is correct
14 Correct 646 ms 53100 KB Output is correct
15 Correct 548 ms 50644 KB Output is correct
16 Correct 700 ms 66300 KB Output is correct
17 Correct 819 ms 64492 KB Output is correct
18 Correct 625 ms 59912 KB Output is correct
19 Correct 624 ms 66668 KB Output is correct
20 Correct 520 ms 60908 KB Output is correct
21 Correct 726 ms 124588 KB Output is correct
22 Correct 613 ms 60012 KB Output is correct
23 Correct 575 ms 63084 KB Output is correct
24 Correct 473 ms 60652 KB Output is correct
25 Correct 667 ms 56428 KB Output is correct
26 Correct 611 ms 70252 KB Output is correct
27 Correct 551 ms 70124 KB Output is correct
28 Correct 377 ms 62444 KB Output is correct
29 Correct 564 ms 67448 KB Output is correct
30 Correct 635 ms 110676 KB Output is correct