oj.uz

Submission #366954

# Submission time Handle Problem Language Result Execution time Memory
366954 2021-02-15T20:18:32 Z dolphingarlic Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 862 ms 77548 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, t, m;
vector<int> graph[1000001];
ll dp[1000001], ans = 0;

bool dfs(int node = t, int parent = 0) {
    bool ret = false;
    ll mx1 = 0, mx2 = 0;
    for (int i : graph[node]) if (i != parent) {
        ret |= dfs(i, node);
        if (dp[i] >= mx1) mx2 = mx1, mx1 = dp[i];
        else if (dp[i] > mx2) mx2 = dp[i];
    }
    dp[node] = graph[node].size() - 1 + mx2;
    if (node == m) return ans += dp[node], true;
    else return ans += (int(graph[node].size()) - 2) * ret, ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> t >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    ans = -int(graph[t].size()) + 2;
    dfs();
    cout << ans;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23800 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23992 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 76660 KB Output is correct
2 Correct 332 ms 71148 KB Output is correct
3 Correct 841 ms 77548 KB Output is correct
4 Correct 386 ms 50432 KB Output is correct
5 Correct 862 ms 77420 KB Output is correct
6 Correct 839 ms 77504 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23800 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23992 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Incorrect 16 ms 23788 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23800 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23992 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Correct 350 ms 76660 KB Output is correct
12 Correct 332 ms 71148 KB Output is correct
13 Correct 841 ms 77548 KB Output is correct
14 Correct 386 ms 50432 KB Output is correct
15 Correct 862 ms 77420 KB Output is correct
16 Correct 839 ms 77504 KB Output is correct
17 Incorrect 16 ms 23788 KB Output isn't correct
18 Halted 0 ms 0 KB -