oj.uz

Submission #35888

# Submission time Handle Problem Language Result Execution time Memory
35888 2017-12-02T03:10:11 Z funcsr Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 2089 ms 62676 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define pb push_back
#define all(xs) xs.begin(), xs.end()
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;

int N, T, M;
vector<int> G[1000000];
int dp[1000000];
bool sub[1000000];

void dfs(int x, int p) {
  vector<int> values;
  int ctr = 0, ti = -1;
  sub[x] = x == M;
  for (int t : G[x]) {
    if (t == p) continue;
    dfs(t, x);
    sub[x] |= sub[t];
    if (sub[t]) ti = t;
    values.pb(dp[t]);
    ctr++;
  }
  if (ti != -1) {
    dp[x] = dp[ti];
    if (p != -1) dp[x] += ctr-1;
    return;
  }
  sort(all(values), greater<int>());
  if (values.size() >= 2) ctr += values[1];
  dp[x] = ctr;
}

signed main() {
  cin >> N >> T >> M;
  T--, M--;
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  dfs(T, -1);
  cout << dp[T] << "\n";
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30336 KB Output is correct
2 Correct 13 ms 30336 KB Output is correct
3 Correct 9 ms 30336 KB Output is correct
4 Correct 9 ms 30336 KB Output is correct
5 Correct 3 ms 30336 KB Output is correct
6 Correct 6 ms 30336 KB Output is correct
7 Correct 0 ms 30336 KB Output is correct
8 Correct 3 ms 30336 KB Output is correct
9 Correct 6 ms 30336 KB Output is correct
10 Correct 9 ms 30336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 61620 KB Output is correct
2 Correct 1029 ms 58452 KB Output is correct
3 Correct 1983 ms 62676 KB Output is correct
4 Correct 856 ms 46572 KB Output is correct
5 Correct 2089 ms 62676 KB Output is correct
6 Correct 1999 ms 62676 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30336 KB Output is correct
2 Correct 13 ms 30336 KB Output is correct
3 Correct 9 ms 30336 KB Output is correct
4 Correct 9 ms 30336 KB Output is correct
5 Correct 3 ms 30336 KB Output is correct
6 Correct 6 ms 30336 KB Output is correct
7 Correct 0 ms 30336 KB Output is correct
8 Correct 3 ms 30336 KB Output is correct
9 Correct 6 ms 30336 KB Output is correct
10 Correct 9 ms 30336 KB Output is correct
11 Correct 1079 ms 61620 KB Output is correct
12 Correct 1029 ms 58452 KB Output is correct
13 Correct 1983 ms 62676 KB Output is correct
14 Correct 856 ms 46572 KB Output is correct
15 Correct 2089 ms 62676 KB Output is correct
16 Correct 1999 ms 62676 KB Output is correct
17 Incorrect 6 ms 30336 KB Output isn't correct
18 Halted 0 ms 0 KB -