oj.uz

Submission #1100871

# Submission time Handle Problem Language Result Execution time Memory
1100871 2024-10-14T20:55:41 Z Kirill22 Balanced Tree (info1cup18_balancedtree) C++17
0 / 100
 2428 ms 57956 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;
        }
        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][k2];
//            if (i2 == 1 && j2 == 1 && k2 == 0) {
//                debug(bdp);
//            }
            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 (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][...]
                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);
//            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);
        }
    }
}

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) {
            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 5 ms 14928 KB Output isn't correct
2 Incorrect 7 ms 14940 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 188 ms 18512 KB Invalid color
3 Incorrect 145 ms 15184 KB Invalid color

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 14928 KB Invalid color
2 Incorrect 238 ms 35288 KB Unexpected end of file - int32 expected
3 Incorrect 135 ms 23888 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 17744 KB Invalid color
2 Incorrect 112 ms 14928 KB Invalid color
3 Incorrect 108 ms 15100 KB Invalid color
4 Incorrect 70 ms 15000 KB Invalid color
5 Incorrect 89 ms 14928 KB Invalid color
6 Incorrect 148 ms 15184 KB Invalid color
7 Incorrect 121 ms 15096 KB Invalid color
8 Incorrect 70 ms 14928 KB Invalid color
9 Incorrect 89 ms 15084 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 14928 KB Output isn't correct
2 Incorrect 7 ms 14940 KB Invalid color
3 Incorrect 65 ms 14928 KB Invalid color
4 Incorrect 188 ms 18512 KB Invalid color
5 Incorrect 145 ms 15184 KB Invalid color
6 Incorrect 83 ms 14928 KB Invalid color
7 Incorrect 238 ms 35288 KB Unexpected end of file - int32 expected
8 Incorrect 135 ms 23888 KB Invalid color
9 Incorrect 164 ms 17744 KB Invalid color
10 Incorrect 112 ms 14928 KB Invalid color
11 Incorrect 108 ms 15100 KB Invalid color
12 Incorrect 70 ms 15000 KB Invalid color
13 Incorrect 89 ms 14928 KB Invalid color
14 Incorrect 148 ms 15184 KB Invalid color
15 Incorrect 121 ms 15096 KB Invalid color
16 Incorrect 70 ms 14928 KB Invalid color
17 Incorrect 89 ms 15084 KB Invalid color
18 Incorrect 862 ms 15432 KB Invalid color
19 Incorrect 999 ms 22556 KB Invalid color
20 Incorrect 339 ms 14928 KB Invalid color
21 Incorrect 2428 ms 53836 KB Unexpected end of file - int32 expected
22 Incorrect 1199 ms 57956 KB Invalid color