oj.uz

Submission #1100873

# Submission time Handle Problem Language Result Execution time Memory
1100873 2024-10-14T21:04:36 Z Kirill22 Balanced Tree (info1cup18_balancedtree) C++17
65.2 / 100
 2475 ms 58952 KB 
#include "bits/stdc++.h"

using namespace std;

//#include "debug.h"

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 == 2) {
            val = 0;
        }
        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);
//    debug(b.dp[1][1][0]);
    for (auto [i, j, k] : states) {
        if (a.dp[i][j][k] == inf) {
            continue;
        }
//        debug(a.dp[1][1][2]);
        int _i = i, _j = j, _k = k;
        for (auto [i2, j2, k2] : states) {
            i = _i, j = _j, k = _k;
            if (b.dp[i2][j2][k2] == inf) {
                continue;
            }
            int adp = a.dp[i][j][k];
            int bdp = b.dp[i2][j2][k2];
//            if (i2 == 1 && j2 == 1 && k2 == 0) {
//                debug(bdp);
//            }
            bdp++;
//            debug(i, j, k, i2, j2, k2, adp, bdp, res.dp[1][1][1]);
            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 (i == 0 && j == 1 && k == 2 && i2 == 1 && j2 == 1 && k2 == 0) {
//                    debug(adp, bdp);
//                }
                if (k2 != 2 && bdp <= K) {
                    j = 1;
                    k2 = 1;
                }
                if (k != 2 && adp + 1 <= K) {
                    j2 = 1;
                    k = 1;
                }
                if (!k2 || (!j2 && 1 >= K) || (!k && adp >= K)) {
                    continue;
                }
                // res[i][j][...]
//                debug(k);
                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);
                }
            }
//            debug(i, j, k, i2, j2, k2, adp, bdp, res.dp[1][1][1]);
        }
    }
    return res;
}

void dfs(int v, int pr) {
    dp[v].init(a[v]);
    for (auto u : g[v]) {
        if (u != pr) {
            dfs(u, v);
//            if (v == 1 && u == 3) {
//                debug(dp[v].dp[0][1][2]);
//                debug(dp[u].dp[1][1][0]);
//            }
            dp[v] = merge(dp[v], dp[u]);
//            debug(v);
        }
    }
//    debug(v);
}

bool check(int _) {
    K = _;
//    debug(K);
    dfs(0, 0);
//    if (K == 6) {
//        debug(dp[0].dp[1][1][1]);
//        debug(dp[3].dp[1][1][0]);
//        debug(dp[1].dp[0][1][1]);
//        debug(dp[2].dp[0][0][2]);
//    }
    for (int it = 0; it < 2; it++) {
        if (dp[0].dp[it][1][1] != inf) {
//            debug(1);exit(0);
            return true;
        }
        if (dp[0].dp[it][1][2] != inf) {
//            debug(2); exit(0);
            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
6.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14928 KB Output is partially correct
2 Correct 7 ms 14928 KB Output is partially correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15092 KB Output is correct
2 Correct 188 ms 18760 KB Output is correct
3 Correct 145 ms 15432 KB Output is correct

Subtask #3
15.6 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 15176 KB Output is partially correct
2 Correct 203 ms 35656 KB Output is partially correct
3 Correct 135 ms 23888 KB Output is partially correct

Subtask #4
27.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 17992 KB Output is partially correct
2 Correct 105 ms 15176 KB Output is partially correct
3 Correct 114 ms 15176 KB Output is partially correct
4 Correct 74 ms 15184 KB Output is partially correct
5 Correct 101 ms 15176 KB Output is partially correct
6 Correct 150 ms 15228 KB Output is partially correct
7 Correct 109 ms 15176 KB Output is partially correct
8 Correct 73 ms 15180 KB Output is partially correct
9 Correct 90 ms 15128 KB Output is partially correct

Subtask #5
3.6 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14928 KB Output is partially correct
2 Correct 7 ms 14928 KB Output is partially correct
3 Correct 66 ms 15092 KB Output is correct
4 Correct 188 ms 18760 KB Output is correct
5 Correct 145 ms 15432 KB Output is correct
6 Correct 87 ms 15176 KB Output is partially correct
7 Correct 203 ms 35656 KB Output is partially correct
8 Correct 135 ms 23888 KB Output is partially correct
9 Correct 163 ms 17992 KB Output is partially correct
10 Correct 105 ms 15176 KB Output is partially correct
11 Correct 114 ms 15176 KB Output is partially correct
12 Correct 74 ms 15184 KB Output is partially correct
13 Correct 101 ms 15176 KB Output is partially correct
14 Correct 150 ms 15228 KB Output is partially correct
15 Correct 109 ms 15176 KB Output is partially correct
16 Correct 73 ms 15180 KB Output is partially correct
17 Correct 90 ms 15128 KB Output is partially correct
18 Correct 901 ms 16344 KB Output is partially correct
19 Correct 1027 ms 23496 KB Output is partially correct
20 Correct 395 ms 15788 KB Output is partially correct
21 Correct 2475 ms 54608 KB Output is partially correct
22 Correct 1158 ms 58952 KB Output is partially correct