oj.uz

Submission #1100872

# Submission time Handle Problem Language Result Execution time Memory
1100872 2024-10-14T21:04:04 Z Kirill22 Balanced Tree (info1cup18_balancedtree) C++17
0 / 100
 2330 ms 57968 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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 14928 KB Output isn't correct
2 Incorrect 7 ms 15012 KB Invalid color

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 14928 KB Invalid color
2 Incorrect 187 ms 18512 KB Invalid color
3 Incorrect 141 ms 15184 KB Invalid color

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 14928 KB Invalid color
2 Incorrect 192 ms 35400 KB Unexpected end of file - int32 expected
3 Incorrect 128 ms 23888 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 17744 KB Invalid color
2 Incorrect 101 ms 15064 KB Invalid color
3 Incorrect 124 ms 15096 KB Invalid color
4 Incorrect 68 ms 14928 KB Invalid color
5 Incorrect 87 ms 14928 KB Invalid color
6 Incorrect 149 ms 15432 KB Invalid color
7 Incorrect 106 ms 14928 KB Invalid color
8 Incorrect 70 ms 14928 KB Invalid color
9 Incorrect 87 ms 15076 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 14928 KB Output isn't correct
2 Incorrect 7 ms 15012 KB Invalid color
3 Incorrect 65 ms 14928 KB Invalid color
4 Incorrect 187 ms 18512 KB Invalid color
5 Incorrect 141 ms 15184 KB Invalid color
6 Incorrect 80 ms 14928 KB Invalid color
7 Incorrect 192 ms 35400 KB Unexpected end of file - int32 expected
8 Incorrect 128 ms 23888 KB Invalid color
9 Incorrect 158 ms 17744 KB Invalid color
10 Incorrect 101 ms 15064 KB Invalid color
11 Incorrect 124 ms 15096 KB Invalid color
12 Incorrect 68 ms 14928 KB Invalid color
13 Incorrect 87 ms 14928 KB Invalid color
14 Incorrect 149 ms 15432 KB Invalid color
15 Incorrect 106 ms 14928 KB Invalid color
16 Incorrect 70 ms 14928 KB Invalid color
17 Incorrect 87 ms 15076 KB Invalid color
18 Incorrect 872 ms 15444 KB Invalid color
19 Incorrect 1010 ms 22544 KB Invalid color
20 Incorrect 461 ms 15008 KB Invalid color
21 Incorrect 2330 ms 53844 KB Unexpected end of file - int32 expected
22 Incorrect 1173 ms 57968 KB Invalid color