oj.uz

Submission #391200

# Submission time Handle Problem Language Result Execution time Memory
391200 2021-04-18T08:20:27 Z palilo Triumphal arch (POI13_luk) C++17
100 / 100
 559 ms 24388 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = n - 1, u, v; i--;) {
        cin >> u >> v, --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    auto vtx = [&](int src) {
        vector<int> stk = {src}, vtx(n);

        for (int i = 0; i < n; ++i) {
            const auto u = stk.back();
            stk.pop_back();

            vtx[i] = u;
            for (const auto& v : adj[u]) {
                adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
                stk.emplace_back(v);
            }
        }
        reverse(vtx.begin(), vtx.end());
        return vtx;
    }(0);

    vector<int> dp(n);
    auto valid = [&](int mid) {
        for (const auto& u : vtx) {
            dp[u] = accumulate(adj[u].begin(), adj[u].end(), 0, [&](auto& sum, auto& v) {
                return sum + dp[v] + 1;
            });
            dp[u] = dp[u] < mid ? 0 : dp[u] - mid;
        }
        return dp[0] == 0;
    };

    int lo = 0, hi = n;
    while (lo != hi) {
        int mid = (lo + hi) >> 1;
        valid(mid) ? hi = mid : lo = mid + 1;
    }
    cout << lo;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 976 KB Output is correct
2 Correct 9 ms 972 KB Output is correct
3 Correct 6 ms 1096 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2508 KB Output is correct
2 Correct 19 ms 2556 KB Output is correct
3 Correct 14 ms 2692 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7916 KB Output is correct
2 Correct 87 ms 7788 KB Output is correct
3 Correct 52 ms 8300 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 15652 KB Output is correct
2 Correct 263 ms 15596 KB Output is correct
3 Correct 136 ms 16324 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 23532 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 23544 KB Output is correct
2 Correct 472 ms 23116 KB Output is correct
3 Correct 319 ms 24388 KB Output is correct