Submission #468681

#	Time	Username	Problem	Language	Result	Execution time	Memory
468681		wdjpng	Mousetrap (CEOI17_mousetrap)	C++17	25 / 100	935 ms	62984 KiB

mousetrap

#include <bits/stdc++.h>
//#define double double
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()

using namespace std;
vector<vector<int>>E;
int t,m;

int dfs(int v, int p)
{
    priority_queue<int>pq;
    int children = 0;
    for(int w : E[v])
    {
        if(w==p||w==t) continue; 
        children++;
        pq.push(-dfs(w,v));
        if(pq.size()>2) pq.pop();
    }

    int sum = min((int)1, children); //block biggest child
    if(children>1)
    {
        sum-=pq.top()-1; // cost of second biggest child + cleaning
        sum+=children-2; // block children 3 .. children
    }
    return sum;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n>>t>>m;
    t--;
    m--;

    E.resize(n);
    rep(i, n-1)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    cout<<dfs(m, -1);
}

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