oj.uz

답안 #468679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468679 2021-08-29T10:49:33 Z wdjpng Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 375 ms 63004 KB 
#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(); // second biggest child
        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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 375 ms 63004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -