oj.uz

Submission #468713

# Submission time Handle Problem Language Result Execution time Memory
468713 2021-08-29T13:12:21 Z paga2004 Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 920 ms 86400 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";
}

Compilation message

mousetrap.cpp: In function 'std::pair<bool, long long int> dfs1(long long int, long long int)':
mousetrap.cpp:31:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     auto [f, s] = dfs1(w, v);
      |          ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 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 391 ms 86400 KB Output is correct
2 Correct 354 ms 78156 KB Output is correct
3 Correct 904 ms 84988 KB Output is correct
4 Correct 421 ms 42768 KB Output is correct
5 Correct 920 ms 85192 KB Output is correct
6 Correct 920 ms 85008 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 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 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 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 391 ms 86400 KB Output is correct
12 Correct 354 ms 78156 KB Output is correct
13 Correct 904 ms 84988 KB Output is correct
14 Correct 421 ms 42768 KB Output is correct
15 Correct 920 ms 85192 KB Output is correct
16 Correct 920 ms 85008 KB Output is correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -