oj.uz

Submission #468681

# Submission time Handle Problem Language Result Execution time Memory
468681 2021-08-29T10:55:36 Z wdjpng Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 935 ms 62984 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()-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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 62984 KB Output is correct
2 Correct 390 ms 56984 KB Output is correct
3 Correct 914 ms 61388 KB Output is correct
4 Correct 431 ms 30972 KB Output is correct
5 Correct 903 ms 61368 KB Output is correct
6 Correct 935 ms 61368 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -