Submission #563700

#	Time	Username	Problem	Language	Result	Execution time	Memory
563700		hoanghq2004	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	694 ms	73324 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, S, T;
vector <int> g[N];
int f[N];

void dfs(int u, int p) {
    int best[3] = {0, 0, 0};
    for (auto v: g[u]) {
        if (v == p) continue;
        dfs(v, u);
        best[2] = f[v];
        sort(best, best + 3);
        reverse(best, best + 3);
    }
    f[u] = best[1] + g[u].size() - 1;
}

int main() {
//    freopen("mousetrap.inp", "r", stdin);
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> S >> T;
    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, S);
    cout << f[T] << '\n';
}

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