oj.uz

Submission #374477

# Submission time Handle Problem Language Result Execution time Memory
374477 2021-03-07T10:24:54 Z ne4eHbKa Svjetlo (COCI20_svjetlo) C++17
110 / 110
 855 ms 124500 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];
    }
    queue<int> q;
    for(int i = 0; i < n; ++i)
        if(e[i] == 1) q.push(i);
    int cnt = 0;
    for(;;) {
        ++cnt;
        assert(!q.empty());
        int v = q.front();
        q.pop();
        mk[v] = true;
        unlit[v] = p[v];
        h.clear();
        for(int u : g[v]) {
            if(--e[u] == 1)
                q.push(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 9 ms 12268 KB Output is correct
2 Correct 10 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 9 ms 12268 KB Output is correct
6 Correct 9 ms 12288 KB Output is correct
7 Correct 8 ms 12268 KB Output is correct
8 Correct 8 ms 12268 KB Output is correct
9 Correct 9 ms 12268 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 40940 KB Output is correct
2 Correct 671 ms 52972 KB Output is correct
3 Correct 644 ms 51564 KB Output is correct
4 Correct 600 ms 48680 KB Output is correct
5 Correct 672 ms 53228 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 50488 KB Output is correct
2 Correct 727 ms 66168 KB Output is correct
3 Correct 855 ms 64364 KB Output is correct
4 Correct 640 ms 59756 KB Output is correct
5 Correct 639 ms 66796 KB Output is correct
6 Correct 543 ms 61036 KB Output is correct
7 Correct 755 ms 124500 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 10 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 9 ms 12268 KB Output is correct
6 Correct 9 ms 12288 KB Output is correct
7 Correct 8 ms 12268 KB Output is correct
8 Correct 8 ms 12268 KB Output is correct
9 Correct 9 ms 12268 KB Output is correct
10 Correct 452 ms 40940 KB Output is correct
11 Correct 671 ms 52972 KB Output is correct
12 Correct 644 ms 51564 KB Output is correct
13 Correct 600 ms 48680 KB Output is correct
14 Correct 672 ms 53228 KB Output is correct
15 Correct 566 ms 50488 KB Output is correct
16 Correct 727 ms 66168 KB Output is correct
17 Correct 855 ms 64364 KB Output is correct
18 Correct 640 ms 59756 KB Output is correct
19 Correct 639 ms 66796 KB Output is correct
20 Correct 543 ms 61036 KB Output is correct
21 Correct 755 ms 124500 KB Output is correct
22 Correct 628 ms 60152 KB Output is correct
23 Correct 606 ms 62956 KB Output is correct
24 Correct 500 ms 60780 KB Output is correct
25 Correct 720 ms 56364 KB Output is correct
26 Correct 637 ms 70252 KB Output is correct
27 Correct 571 ms 69996 KB Output is correct
28 Correct 394 ms 62316 KB Output is correct
29 Correct 593 ms 67436 KB Output is correct
30 Correct 661 ms 110808 KB Output is correct