oj.uz

Submission #571617

# Submission time Handle Problem Language Result Execution time Memory
571617 2022-06-02T12:20:28 Z piOOE Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 793 ms 92224 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], depth[N], deg[N], gg[N], sum_deg[N];
vector<int> tops;

void dfs(int v, int p) {
    parent[v] = p;
    int mx1 = 0, mx2 = 0;
    deg[v] = (p == v ? sz(g[v]) : sz(g[v]) - 1);
    sum_deg[v] = sum_deg[p] + (p == v ? 1 : deg[v]);
    for (int to: g[v]) {
        if (to != p) {
            depth[to] = depth[v] + 1;
            dfs(to, v);
            if (mx1 < dp[to]) {
                mx2 = mx1;
                mx1 = dp[to];
            } else if (mx2 < dp[to]) {
                mx2 = dp[to];
            }
        }
    }
    dp[v] = mx2 + deg[v];
    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 = n * 3;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        int x = m, prv = -1;
        int total = sum_deg[m] - depth[m];
        bool ok = total <= mid;
        int can = 0;
        while (ok && x != t) {
            ++can;
            int cnt = 0;
            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 13 ms 23812 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 14 ms 23848 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23792 KB Output is correct
7 Correct 13 ms 23768 KB Output is correct
8 Correct 15 ms 23816 KB Output is correct
9 Correct 13 ms 23812 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 90468 KB Output is correct
2 Correct 273 ms 85252 KB Output is correct
3 Correct 793 ms 92152 KB Output is correct
4 Correct 345 ms 58500 KB Output is correct
5 Correct 708 ms 92224 KB Output is correct
6 Correct 726 ms 92192 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23812 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 14 ms 23848 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23792 KB Output is correct
7 Correct 13 ms 23768 KB Output is correct
8 Correct 15 ms 23816 KB Output is correct
9 Correct 13 ms 23812 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct
11 Incorrect 12 ms 23764 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23812 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 14 ms 23848 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23792 KB Output is correct
7 Correct 13 ms 23768 KB Output is correct
8 Correct 15 ms 23816 KB Output is correct
9 Correct 13 ms 23812 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct
11 Correct 306 ms 90468 KB Output is correct
12 Correct 273 ms 85252 KB Output is correct
13 Correct 793 ms 92152 KB Output is correct
14 Correct 345 ms 58500 KB Output is correct
15 Correct 708 ms 92224 KB Output is correct
16 Correct 726 ms 92192 KB Output is correct
17 Incorrect 12 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -