Submission #559132

#	Time	Username	Problem	Language	Result	Execution time	Memory
559132		fatemetmhr	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	721 ms	60108 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back

const int maxn5 = 1e6 + 10;

int tale, mo, dp[maxn5];
vector <int> adj[maxn5];

inline bool dfs(int v, int par){
    int z = -1;
    for(auto u : adj[v]) if(u != par){
        bool re = dfs(u, v);
        if(re){
            z = u;
        }
    }
    if(v == mo){
        if(adj[v].size() == 1){
            dp[v] = 0;
            return true;
        }
        int mx = 0;
        for(auto u : adj[v]) if(u != par){
            dp[v] += dp[u];
            mx = max(mx, dp[u]);
        }
        dp[v] = min(dp[v] - mx + 1, dp[v]);
        return true;
    }
    if(v == tale){
        dp[v] = dp[z];
        return true;
    }
    if(z == -1){
        int mx = 0;
        for(auto u : adj[v]) if(u != par){
            dp[v] += dp[u];
            mx = max(mx, dp[u]);
        }
        dp[v] = min(dp[v] - mx + 1, dp[v]) + 1;
        return false;
    }
    int mx = 0;
    for(auto u : adj[v]) if(u != par){
        dp[v] += dp[u];
        if(z != u)
            mx = max(mx, dp[u]);
    }
    dp[v] = min(dp[v] - mx + 1, dp[v]);
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, a, b; cin >> n >> a >> b;
    a--; b--;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    assert(a != b);

    if(a == b)
        return cout << 0 << endl, 0;

    mo = b;
    tale = a;
    dfs(a, -1);
    cout << dp[a] << endl;
}

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