Submission #1111163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111163		Ghulam_Junaid	Mousetrap (CEOI17_mousetrap)	C++17	25 / 100	893 ms	81224 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
 
int n, t, m, dp[N], par[N], cnt_child[N];
vector<int> g[N];
 
void dfs(int v, int p = -1){
    int mx = 0;
    int mx2 = 0;
 
    par[v] = p;
    int children = 0;
    for (int u : g[v]){
        if (u == p) continue;
 
        children++;
        dfs(u, v);
 
        mx2 = max(mx2, dp[u]);
        if (mx < mx2)
            swap(mx, mx2);
    }
 
    // cout << "for v = " << v << " : " << children << " " << mx2 << endl;
    cnt_child[v] = children;
    dp[v] = children + mx2;
    // cout << dp[v] << endl;
}
 
int main(){
    cin >> n >> t >> m;
 
    for (int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
 
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    dfs(t);
 
    int cur = m;
    while (par[cur] != -1){
        cur = par[cur];
        dp[m] += cnt_child[cur] - 1;
    }
 
    cout << dp[m] << endl;
}

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