oj.uz

Submission #468714

# Submission time Handle Problem Language Result Execution time Memory
468714 2021-08-29T13:12:55 Z paga2004 Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 932 ms 86396 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

#ifdef LOCAL
#define dbg(x) cerr << x << "\n";
#else
#define dbg(x)
#endif

const int INF = 1e17;

int n, t, m;
vector<int> scores;
vector<vector<int>> g;
vector<int> depths, parent;

pair<bool, int> dfs1(int v, int p) {
  parent[v] = p;
  bool flag = v == m;
  depths[v] = depths[p] + max(0ll, (int)g[v].size() - 2);
  if (v == t) {
    depths[v] = 0;
  }
  vector<int> besties;
  for (int w : g[v]) {
    if (w == p)
      continue;
    auto [f, s] = dfs1(w, v);
    if (f) {
      flag = true;
      continue;
    }
    besties.push_back(s);
  }
  sort(besties.begin(), besties.end());
  int score = besties.size();
  if (v == t) {
    score = 0;
  }
  if (besties.size() >= 2) {
    score += besties[besties.size() - 2];
  }
  if (flag)
    score--;
  if (v == m)
    score++;
  scores[v] = score;
  return {flag, score};
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> t >> m;
  t--;
  m--;
  if (t == m) {
    cout << "0\n";
    exit(0);
  }

  g.resize(n);
  scores.resize(n);
  depths.resize(n);
  parent.resize(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  dfs1(t, t);
  /* dbg("scores"); */
  /* for (int i = 0; i < n; i++) { */
  /*   cout << scores[i] << " "; */
  /* } */
  /* cout << "\n"; */
  /* dbg("depths"); */
  /* for (int i = 0; i < n; i++) { */
  /*   cout << depths[i] << " "; */
  /* } */
  /* cout << "\n"; */

  int best = 0;
  while (parent[m] != m) {
    best = max(best, scores[m] + depths[parent[m]]);
    m = parent[m];
  }

  cout << best << "\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 86396 KB Output is correct
2 Correct 351 ms 77892 KB Output is correct
3 Correct 932 ms 84788 KB Output is correct
4 Correct 430 ms 42564 KB Output is correct
5 Correct 907 ms 84604 KB Output is correct
6 Correct 925 ms 84804 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 398 ms 86396 KB Output is correct
12 Correct 351 ms 77892 KB Output is correct
13 Correct 932 ms 84788 KB Output is correct
14 Correct 430 ms 42564 KB Output is correct
15 Correct 907 ms 84604 KB Output is correct
16 Correct 925 ms 84804 KB Output is correct
17 Incorrect 0 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -