제출 #1264487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264487		biank	Mousetrap (CEOI17_mousetrap)	C++20	100 / 100	483 ms	156924 KiB

mousetrap

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define foreach(it, c) for (auto it = begin(c); it != end(c); it++)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

using vi = vector<int>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using ii = pair<int, int>;

#define fst first
#define snd second

const int MAX_N = 1e6 + 20;

vi adj[MAX_N];
int dp[MAX_N], par[MAX_N];

void dfs0(int u, int p = -1) {
    par[u] = p;
    for (int v : adj[u]) {
        if (v != p) dfs0(v, u);
    }
}

void dfs(int u, int p) {
    int maxi = 0, sndMaxi = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        if (dp[v] >= maxi) {
            sndMaxi = maxi;
            maxi = dp[v];
        } else if (dp[v] > sndMaxi) {
            sndMaxi = dp[v];
        }
    }
    dp[u] = sndMaxi + sz(adj[u]) - 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, t, m;
    cin >> n >> t >> m;
    --t, --m;
    
    forn(i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs0(t);
    vi path{m};
    while (path.back() != t) path.pb(par[path.back()]);
    vector<bool> inPath(n);
    for (int u : path) inPath[u] = true; 
    vector<vi> l;
    l.reserve(sz(path));
    for (int u : path) {
        vi vals;
        for (int v : adj[u]) {
            if (inPath[v]) continue;
            dfs(v, u);
            vals.pb(dp[v]);
        }
        sort(all(vals), greater<int>());
        l.pb(vals);
    }
    vi suff(sz(path));
    suff[sz(path) - 1] = 0;
    dforn(i, sz(path) - 1) suff[i] = suff[i + 1] + sz(l[i]);
    auto check = [&](int moves) {
        int toUse = 1;
        forn(i, sz(path) - 1) {
            int blocked = 0;
            for (auto val : l[i]) {
                if (val + suff[i] - blocked > moves) {
                    if (!toUse || !moves) return false;
                    toUse--, moves--, blocked++;
                }
            }
            toUse++;
        }
        return true;
    };
    int lo = -1, hi = 1e9;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << '\n';
    
    return 0;
}

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