Submission #596782

#	Time	Username	Problem	Language	Result	Execution time	Memory
596782		1bin	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	864 ms	166320 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e6 + 5;
int n, t, m, u, v, d, dp[NMAX], inP[NMAX];
vector<int> adj[NMAX], P;

int dfs(int x, int p){
    int ret = x == m;
    for(int nx : adj[x]){
        if(nx == p) continue;
        ret |= dfs(nx, x);
    }
    if(ret) P.emplace_back(x), inP[x] = 1;
    return ret;
}

void dfs2(int x, int p){
    int deg, mx1, mx2, t;
    deg = mx1 = mx2 = 0;
    
    for(int nx : adj[x]){
        if(nx == p) continue;
        dfs2(nx, x); deg++;
        t = dp[nx];
        if(t > mx2) mx2 = t;
        if(mx2 > mx1) swap(mx1, mx2);
    }
    dp[x] = mx2 + deg;
    return;
}

int go(int m){
    int cnt = 0, b = 0, deg = d;
    
    for(int p : P){
        int t = 0; cnt++;
        for(int x: adj[p]) {
            if(inP[x]) continue;
            if(dp[x] + deg > m) b++;
            else t++;
        }
        if(b > cnt) return 0;
        deg -= t;
    }
    return 1;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> t >> m;
    for(int i = 0; i < n - 1; i++){
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    
    dfs(t, -1); P.pop_back();
    for(int p : P)
        for(int x : adj[p]) 
            if(!inP[x]) dfs2(x, p), d++;
    
    int l = d, r = 2 * n;
    while(l < r){
        int m = (l + r) >> 1;
        if(go(m)) r = m;
        else l = m + 1;
    }
    cout << l;
    return 0;
}

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