oj.uz

Submission #784623

# Submission time Handle Problem Language Result Execution time Memory
784623 2023-07-16T11:14:02 Z cadmiumsky Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 792 ms 77300 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e6 + 5;

int dp[nmax], p[nmax];
vector<int> g[nmax];

vector<vector<int>> adj;

void initp(int node, int f) {
  p[node] = f;
  for(auto x : g[node]) if(x != f) initp(x, node);
}

void initdp(int node, int f) {
  //cerr << node << '\n';
  vector<int> vs;
  for(auto x : g[node]) {
    if(x == f) continue;
    initdp(x, node);
    vs.emplace_back(dp[x]);
  }
  sort(all(vs));
  if(sz(vs) < 2) dp[node] = 1;
  else dp[node] = sz(vs) + rbegin(vs)[1];
  return;
}

bool crapa(int threshold) {
  int tolerance = 1;
  for(int i = 0; i < sz(adj); tolerance++, i++) {
    int cnt = 0;
    for(auto x : adj[i])
      if(x > threshold) cnt++, tolerance--;
      else break;
    threshold -= cnt;
    if(tolerance < 0 || threshold < 0) return 1;
  }
  return 0;
  
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, T, M;
  cin >> n >> T >> M;
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  
  initp(T, T);
  int prv = -1;
  while(M != T) {
    adj.emplace_back();
    for(auto x : g[M]) {
      if(x == p[M] || x == prv) continue;
      initdp(x, M);
      adj.back().emplace_back(dp[x]);
    }
    prv = M;
    M = p[M];
    sort(all(adj.back()), greater<int>());
  }
  
  int sum = -1;
  for(int i = 0; i < sz(adj); i++) {
    sum += sz(rbegin(adj)[i]);
    for(auto &x : rbegin(adj)[i]) x += sum;
  }
  
  int lim = -1;
  for(int step = 21; step >= 0; step--)
    if(crapa(lim + (1 << step))) lim += (1 << step);
  
  cout << lim + 1 << '\n';;
  
}

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 12 ms 23716 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23736 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Incorrect 12 ms 23780 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 63424 KB Output is correct
2 Correct 227 ms 70964 KB Output is correct
3 Correct 792 ms 77300 KB Output is correct
4 Incorrect 331 ms 50308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 12 ms 23716 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23736 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Incorrect 12 ms 23780 KB Output isn't correct
10 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 14 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 12 ms 23716 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23736 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Incorrect 12 ms 23780 KB Output isn't correct
10 Halted 0 ms 0 KB -