oj.uz

Submission #1100863

# Submission time Handle Problem Language Result Execution time Memory
1100863 2024-10-14T20:29:00 Z Kirill22 Balanced Tree (info1cup18_balancedtree) C++17
0 / 100
 257 ms 64668 KB 
#include "bits/stdc++.h"

using namespace std;

const int N = (int) 5e5 + 22;
const int inf = (int) 1e9;

vector<array<int, 3>> states;
int K;

struct Data {
    int dp[2][2][3]; // bad(tomin), good(tomin), empty(0)

    void init(int x) {
        for (auto [i, j, k] : states) {
            dp[i][j][k] = inf;
        }
        if (x == 0 || x == -1) {
            dp[0][0][2] = 0;
        }
        if (x == 1 || x == -1) {
            dp[1][0][2] = 0;
        }
    }

    void upd(int i, int j, int k, int val) {
        if (k == 0 && val >= K) {
            //
        } else {
            dp[i][j][k] = min(dp[i][j][k], val);
        }
    }
};

int n, a[N];
Data dp[N];
vector<int> g[N];

Data merge(const Data& a, const Data& b) {
    Data res;
    res.init(-2);
    for (auto [i, j, k] : states) {
        if (a.dp[i][j][k] == inf) {
            continue;
        }
        for (auto [i2, j2, k2] : states) {
            if (b.dp[i2][j2][k2] == inf) {
                continue;
            }
            int adp = a.dp[i][j][k];
            int bdp = b.dp[i2][j2][j2];
            bdp++;
            if (i == i2) {
                // dp[i][1]
                if (k == 2 && k2 == 2) {
                    res.upd(i, 1, 2, 0);
                } else if (k == 2) {
                    res.upd(i, 1, k2, bdp);
                } else if (k2 == 2) {
                    res.upd(i, 1, k, adp);
                } else {
                    if (adp + bdp <= K) {
                        k = k2 = 1;
                    }
                    if (k && k2) {
                        res.upd(i, 1, 1, min(adp, bdp));
                    } else {
                        res.upd(i, 1, 0, k ? bdp : k2 ? adp : max(adp, bdp));
                    }
                }
            } else {
                if (k2 != 2 && bdp <= K) {
                    j = 1;
                    k2 = 1;
                }
                if (k != 2 && adp + 1 <= K) {
                    j2 = 1;
                    k = 1;
                }
                if (!k2 || adp >= K) {
                    continue;
                }
                // res[i][j][...]
                if (k == 2) {
                    res.upd(i, j, j2, 1);
                } else if (k == 1) {
                    res.upd(i, j, j2, 1);
                } else {
                    res.upd(i, j, k, adp);
                }
            }
        }
    }
    return res;
}

void dfs(int v, int pr) {
    dp[v].init(a[v]);
    for (auto u : g[v]) {
        if (u != pr) {
            dfs(u, v);
            dp[v] = merge(dp[v], dp[u]);
        }
    }
}

bool check(int _) {
    K = _;
    dfs(0, 0);
    for (int it = 0; it < 2; it++) {
        if (dp[0].dp[it][1][1] != inf) {
            return true;
        }
        if (dp[0].dp[it][1][2] != inf) {
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        g[i].clear();
    }
    for (int i = 0, x, y; i + 1 < n; i++) {
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = 0, r = n;
    if (!check(r)) {
        cout << -1 << '\n';
    } else {
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        cout << r << '\n';
        for (int i = 0; i < n; i++) {
            cout << max(0, a[i]) << " ";
        }
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                states.push_back({i, j, k});
            }
        }
    }
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 14928 KB Output isn't correct
2 Incorrect 6 ms 15096 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 15696 KB Output isn't correct
2 Incorrect 38 ms 20040 KB Output isn't correct
3 Incorrect 29 ms 16464 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 15952 KB Output isn't correct
2 Incorrect 44 ms 36644 KB Output isn't correct
3 Incorrect 36 ms 24824 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 19016 KB Output isn't correct
2 Incorrect 24 ms 16076 KB Output isn't correct
3 Incorrect 27 ms 16208 KB Output isn't correct
4 Incorrect 43 ms 15664 KB Output isn't correct
5 Incorrect 44 ms 15956 KB Output isn't correct
6 Incorrect 29 ms 16208 KB Output isn't correct
7 Incorrect 35 ms 15820 KB Output isn't correct
8 Incorrect 70 ms 15784 KB Output isn't correct
9 Incorrect 72 ms 15944 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 14928 KB Output isn't correct
2 Incorrect 6 ms 15096 KB Output isn't correct
3 Incorrect 37 ms 15696 KB Output isn't correct
4 Incorrect 38 ms 20040 KB Output isn't correct
5 Incorrect 29 ms 16464 KB Output isn't correct
6 Incorrect 23 ms 15952 KB Output isn't correct
7 Incorrect 44 ms 36644 KB Output isn't correct
8 Incorrect 36 ms 24824 KB Output isn't correct
9 Incorrect 32 ms 19016 KB Output isn't correct
10 Incorrect 24 ms 16076 KB Output isn't correct
11 Incorrect 27 ms 16208 KB Output isn't correct
12 Incorrect 43 ms 15664 KB Output isn't correct
13 Incorrect 44 ms 15956 KB Output isn't correct
14 Incorrect 29 ms 16208 KB Output isn't correct
15 Incorrect 35 ms 15820 KB Output isn't correct
16 Incorrect 70 ms 15784 KB Output isn't correct
17 Incorrect 72 ms 15944 KB Output isn't correct
18 Incorrect 154 ms 21424 KB Output isn't correct
19 Incorrect 141 ms 29256 KB Output isn't correct
20 Incorrect 195 ms 19016 KB Output isn't correct
21 Incorrect 257 ms 61256 KB Output isn't correct
22 Incorrect 181 ms 64668 KB Output isn't correct