Submission #151718

#	Time	Username	Problem	Language	Result	Execution time	Memory
151718		forestryks	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	1348 ms	86212 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int MAXN = 1e6 + 5;
int n, t, m;
vector<int> g[MAXN];
int p[MAXN];
bool onp[MAXN];
int h[MAXN];
int sum[MAXN];
int dp[MAXN];

bool pre(int v) {
    for (auto to : g[v]) {
        g[to].erase(find(all(g[to]), v));
        p[to] = v;
        h[to] = h[v] + 1;
        if (pre(to)) {
            onp[v] = true;
        }
    }

    if (v == m || onp[v]) return (onp[v] = true);
    return false;
}

void dfs(int v) {
    sum[v] += g[v].size();
    for (auto to : g[v]) {
        sum[to] += sum[v];
    }

    int mx1 = -1, mx2 = -1;
    for (auto to : g[v]) {
        dfs(to);
        if (dp[to] > mx2) {
            if (dp[to] > mx1) {
                mx2 = mx1;
                mx1 = dp[to];
            } else {
                mx2 = dp[to];
            }
        }
    }

    if (g[v].empty()) {
        dp[v] = 0;
    } else if (mx2 == -1) {
        dp[v] = 1;
    } else {
        dp[v] = mx2 + g[v].size();
    }
}

vector<int> ord;
bool used[MAXN];

bool check(int x) {
    memset(used, 0, sizeof used);
    ord.clear();
    ord.reserve(n);
    int cnt = 0;
    for (int v = m; v != t; v = p[v]) {
        int cnt1 = 0;
        for (auto to : g[v]) {
            if (onp[to]) continue;
            int c = cnt + dp[to] + (sum[v] - h[v] - (v != m));
            if (c > x) {
                ord.push_back(to);
                cnt1++;
            } else {
                used[to] = true;
            }
        }
        cnt += cnt1;
    }

    int ptr = 0;
    for (int v = m; v != t; v = p[v]) {
        if (ptr < ord.size()) {
            used[ord[ptr++]] = true;
        }

        for (auto to : g[v]) {
            if (onp[to]) continue;
            if (!used[to]) return false;
        }
    }

    return true;
}

int main() {
    FAST_IO;
    cin >> n >> t >> m;
    t--; m--;
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    p[t] = -1;
    pre(t);
    dfs(t);

    int l = -1, r = 1e7;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }

    cout << r << endl;
}

Compilation message (stderr)

mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ptr < ord.size()) {
             ~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35