oj.uz

Submission #583477

# Submission time Handle Problem Language Result Execution time Memory
583477 2022-06-25T11:52:13 Z 600Mihnea Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 1129 ms 64076 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 = 0;
  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;
  }
  while (v != tr) {
    int skip = 0, cnt = 0;
    for (auto &oth : g[v]) {
      if (!vis[oth]) {
        skip += (sum + cost[oth] <= limit);
        cnt += (sum + cost[oth] > limit);
      }
    }
    dist++;
    sum -= skip;
    if (cnt > dist) return 0;
    v = par[v];
  }
  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 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 14 ms 23824 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23804 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 14 ms 23876 KB Output is correct
10 Correct 16 ms 23820 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 62944 KB Output is correct
2 Correct 389 ms 59096 KB Output is correct
3 Correct 1129 ms 64032 KB Output is correct
4 Correct 510 ms 44032 KB Output is correct
5 Correct 1075 ms 64032 KB Output is correct
6 Correct 1024 ms 64076 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 14 ms 23824 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23804 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 14 ms 23876 KB Output is correct
10 Correct 16 ms 23820 KB Output is correct
11 Incorrect 12 ms 23764 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 14 ms 23824 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23804 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 14 ms 23876 KB Output is correct
10 Correct 16 ms 23820 KB Output is correct
11 Correct 410 ms 62944 KB Output is correct
12 Correct 389 ms 59096 KB Output is correct
13 Correct 1129 ms 64032 KB Output is correct
14 Correct 510 ms 44032 KB Output is correct
15 Correct 1075 ms 64032 KB Output is correct
16 Correct 1024 ms 64076 KB Output is correct
17 Incorrect 12 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -