oj.uz

Submission #583481

# Submission time Handle Problem Language Result Execution time Memory
583481 2022-06-25T12:00:35 Z 600Mihnea Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 1116 ms 64080 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e6 + 7;
int n, tr, mo;
vector<int> g[N];
int par[N], cost[N];
bool vis[N];

void build_tree(int a, int p = -1) {
  {
    vector<int> Kids;
    for (auto &b : g[a]) {
      if (b != p) {
        Kids.push_back(b);
      }
    }
    g[a] = Kids;
  }
  for (auto &b : g[a]) {
    build_tree(b, a);
  }
  par[a] = p;
}

void build_cost(int a) {
  if (!vis[a] && a != mo) {
    cost[a] += (int) g[a].size();
  }
  for (auto &b : g[a]) {
    cost[b] += cost[a];
    build_cost(b);
  }
}

void dfs(int a) {
  for (auto &b : g[a]) {
    dfs(b);
  }
  if ((int) g[a].size() == 0) {
    return;
  }
  if ((int) g[a].size() == 1) {
    return;
  }
  assert((int) g[a].size() >= 2);
  vector<int> Values;
  for (auto &b : g[a]) {
    Values.push_back(cost[b]);
  }
  sort(Values.rbegin(), Values.rend());
  assert((int) Values.size() >= 2);
  cost[a] = Values[1];
}

bool ok(int limit) {
  vector<pair<int, int>> guys;
  int dist = 1;
  guys.push_back({0, cost[mo]});
  int v = mo;
  int sum = 0;
  {
    for (int i = 1; i <= n; i++) {
      if ((vis[i] && i != tr) || i == mo) {
        sum += (int) g[i].size() - 1;
      }
    }
    sum++;

  }
  if (sum > limit) {
    return 0;
  }
  int cnt = 0;
  while (v != tr) {
    int skip = 0;
    for (auto &oth : g[v]) {
      if (!vis[oth]) {
        skip += (sum + cost[oth] <= limit);
        cnt += (sum + cost[oth] > limit);
      }
    }
    sum -= skip;
    if (cnt > dist) return 0;
    v = par[v];
    dist++;
  }
  return 1;
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

///  freopen ("input.txt", "r", stdin);

  cin >> n >> tr >> mo;

  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  build_tree(tr);
  {
    int current = par[mo];
    while (current != tr) {
      vis[current] = 1;
      current = par[current];
    }
    vis[current] = 1;
  }
  build_cost(tr);
  dfs(tr);


  int low = 0, high = (int) 1e9 + 7, sol = -1;

  while (low <= high) {
    int mid = (low + high) / 2;
    if (ok(mid)) {
      sol = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  assert(sol != -1);

  cout << sol << "\n";

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23712 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 12 ms 23740 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23808 KB Output is correct
7 Correct 14 ms 23752 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 15 ms 23744 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 62896 KB Output is correct
2 Correct 379 ms 59016 KB Output is correct
3 Correct 1116 ms 64080 KB Output is correct
4 Correct 492 ms 43852 KB Output is correct
5 Correct 1002 ms 63952 KB Output is correct
6 Correct 1018 ms 64080 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23712 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 12 ms 23740 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23808 KB Output is correct
7 Correct 14 ms 23752 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 15 ms 23744 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 16 ms 23820 KB Output is correct
13 Correct 13 ms 23824 KB Output is correct
14 Correct 14 ms 23948 KB Output is correct
15 Correct 13 ms 23892 KB Output is correct
16 Correct 13 ms 23764 KB Output is correct
17 Incorrect 14 ms 23816 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23712 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 12 ms 23740 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23808 KB Output is correct
7 Correct 14 ms 23752 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 15 ms 23744 KB Output is correct
11 Correct 426 ms 62896 KB Output is correct
12 Correct 379 ms 59016 KB Output is correct
13 Correct 1116 ms 64080 KB Output is correct
14 Correct 492 ms 43852 KB Output is correct
15 Correct 1002 ms 63952 KB Output is correct
16 Correct 1018 ms 64080 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 16 ms 23820 KB Output is correct
19 Correct 13 ms 23824 KB Output is correct
20 Correct 14 ms 23948 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Correct 13 ms 23764 KB Output is correct
23 Incorrect 14 ms 23816 KB Output isn't correct
24 Halted 0 ms 0 KB -