Submission #784640

#	Time	Username	Problem	Language	Result	Execution time	Memory
784640		cadmiumsky	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	905 ms	185932 KiB

mousetrap

#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] = sz(vs);
  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>());
  }
  
  //for(auto x : adj) {
    //for(auto y : x) cerr << y << ' ';
    //cerr << '\n';
  //}
  int sum = 0;
  for(int i = 0; i < sz(adj); i++) {
    sum += sz(rbegin(adj)[i]);
    for(auto &x : rbegin(adj)[i]) x += sum;
  }
  
  //for(auto x : adj) {
    //for(auto y : x) cerr << y << ' ';
    //cerr << '\n';
  //}
  
  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: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35