Submission #571617

#	Time	Username	Problem	Language	Result	Execution time	Memory
571617		piOOE	Mousetrap (CEOI17_mousetrap)	C++17	45 / 100	793 ms	92224 KiB

mousetrap

#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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35