Submission #1106534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106534		LOLOLO	Mousetrap (CEOI17_mousetrap)	C++14	40 / 100	198 ms	62536 KiB

mousetrap

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e6 + 10;
vector <int> ed[N];
int f[N], n, m, t, on[N], dep[N];

void dfs(int u, int v) {
    vector <int> cost;
    for (auto x : ed[u]) {
        if (x == v)
            continue;

        if (v) {
            f[x] = f[u] + sz(ed[u]) - 2;
        }

        dfs(x, u);
        if (on[x])
            on[u] = 1;

        cost.pb(f[x]);
    }

    sort(all(cost));
    if (sz(cost) > 1) {
        f[u] = cost[1];
    }

    f[u] += (sz(ed[u]) > 1);
}

vector <pair <int, int>> save;

void run(int u, int v) {
    if (u == t)
        return;

    for (auto x : ed[u]) {
        if (x == v)
            continue;

        dep[x] = dep[u] + 1;
        if (on[u] && !on[x]) {
            save.pb({dep[x], f[x] + (u == m)});
        } else {
            run(x, u);
        }
    }
}

bool check(int m) {
    int need = 0;
    for (auto x : save) {
        if (need > x.f)
            return 0;

        if (need + x.s > m) {
            need++;
        }
    }

    return need <= m;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> t >> m;

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }

    on[m] = 1;
    dep[m] = -1;

    dfs(t, 0);
    run(m, 0);
    sort(all(save));

    int l = 0, r = n, ans = 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

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