oj.uz

Submission #468717

# Submission time Handle Problem Language Result Execution time Memory
468717 2021-08-29T13:21:55 Z paga2004 Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 949 ms 86468 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 (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 0 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 86468 KB Output is correct
2 Correct 363 ms 77804 KB Output is correct
3 Correct 928 ms 84848 KB Output is correct
4 Correct 440 ms 42628 KB Output is correct
5 Correct 949 ms 84676 KB Output is correct
6 Correct 930 ms 84792 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 0 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 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 0 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 463 ms 86468 KB Output is correct
12 Correct 363 ms 77804 KB Output is correct
13 Correct 928 ms 84848 KB Output is correct
14 Correct 440 ms 42628 KB Output is correct
15 Correct 949 ms 84676 KB Output is correct
16 Correct 930 ms 84792 KB Output is correct
17 Incorrect 0 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -