oj.uz

Submission #563700

# Submission time Handle Problem Language Result Execution time Memory
563700 2022-05-18T02:49:17 Z hoanghq2004 Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 694 ms 73324 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23764 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 301 ms 72392 KB Output is correct
2 Correct 264 ms 67532 KB Output is correct
3 Correct 691 ms 73316 KB Output is correct
4 Correct 325 ms 48392 KB Output is correct
5 Correct 694 ms 73324 KB Output is correct
6 Correct 690 ms 73320 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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