oj.uz

Submission #571621

# Submission time Handle Problem Language Result Execution time Memory
571621 2022-06-02T12:24:48 Z piOOE Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 933 ms 158700 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int N = 1000001, infI = 1e9 + 7;
const ll infL = 3e18;

int n, t, m;
vector<int> g[N];
int dp[N], parent[N];
vector<int> tops;

void dfs(int v, int p) {
    parent[v] = p;
    int mx1 = 0, mx2 = 0, cnt = 0;
    for (int to: g[v]) {
        if (to != p) {
            ++cnt;
            dfs(to, v);
            if (mx1 < dp[to]) {
                mx2 = mx1;
                mx1 = dp[to];
            } else if (mx2 < dp[to]) {
                mx2 = dp[to];
            }
        }
    }
    dp[v] = mx2 + cnt;
    tops.push_back(v);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> t >> m;
    --t, --m;
    if (t == m) {
        exit(1);
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(t, t);
    int l = -1, r = infI;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        int total = 0;
        {
            int x = m;
            int prv = 0;
            while (x != t) {
                for (int to : g[x]) {
                    if (to != prv && to != parent[x])
                        ++total;
                }
                prv = x;
                x = parent[x];
            }
        }
        int x = m, prv = -1;
        bool ok = total <= mid;
        int can = 0;
        int cnt = 0;
        while (ok && x != t) {
            ++can;
            int nw = 0;
            for (int to: g[x]) {
                if (to != parent[x] && to != prv) {
                    if (dp[to] + total > mid) {
                        ++cnt;
                    } else {
                        ++nw;
                    }
                }
            }
            total -= nw;
            if (cnt > can) {
                ok = false;
            }
            prv = x;
            x = parent[x];
        }
        if (ok) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23752 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 13 ms 23776 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 14 ms 23828 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 12 ms 23716 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 66920 KB Output is correct
2 Correct 248 ms 62656 KB Output is correct
3 Correct 705 ms 68328 KB Output is correct
4 Correct 354 ms 46108 KB Output is correct
5 Correct 689 ms 68296 KB Output is correct
6 Correct 693 ms 68264 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23752 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 13 ms 23776 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 14 ms 23828 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 12 ms 23716 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 15 ms 23892 KB Output is correct
16 Correct 16 ms 23812 KB Output is correct
17 Correct 15 ms 23820 KB Output is correct
18 Correct 14 ms 23796 KB Output is correct
19 Correct 13 ms 23844 KB Output is correct
20 Correct 12 ms 23824 KB Output is correct
21 Correct 14 ms 23764 KB Output is correct
22 Correct 13 ms 23828 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23752 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 13 ms 23776 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 14 ms 23828 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 12 ms 23716 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 262 ms 66920 KB Output is correct
12 Correct 248 ms 62656 KB Output is correct
13 Correct 705 ms 68328 KB Output is correct
14 Correct 354 ms 46108 KB Output is correct
15 Correct 689 ms 68296 KB Output is correct
16 Correct 693 ms 68264 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 13 ms 23892 KB Output is correct
21 Correct 15 ms 23892 KB Output is correct
22 Correct 16 ms 23812 KB Output is correct
23 Correct 15 ms 23820 KB Output is correct
24 Correct 14 ms 23796 KB Output is correct
25 Correct 13 ms 23844 KB Output is correct
26 Correct 12 ms 23824 KB Output is correct
27 Correct 14 ms 23764 KB Output is correct
28 Correct 13 ms 23828 KB Output is correct
29 Correct 12 ms 23764 KB Output is correct
30 Correct 322 ms 80420 KB Output is correct
31 Correct 269 ms 80256 KB Output is correct
32 Correct 593 ms 158700 KB Output is correct
33 Correct 319 ms 158688 KB Output is correct
34 Correct 682 ms 81384 KB Output is correct
35 Correct 711 ms 81580 KB Output is correct
36 Correct 880 ms 88980 KB Output is correct
37 Correct 933 ms 89156 KB Output is correct
38 Correct 597 ms 91896 KB Output is correct
39 Correct 600 ms 91880 KB Output is correct
40 Correct 647 ms 91784 KB Output is correct