Submission #1149022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149022		duckindog	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	445 ms	189380 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n, t, m;
vector<int> ad[N];

vector<int> path;

int f[N];
bool inPath[N];
void dfs(int u, int p = -1) { 
  inPath[u] = (u == t);
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    dfs(v, u);
    inPath[u] |= inPath[v];
  }
  if (inPath[u]) path.push_back(u);

  vector<int> best{0, 0};
  for (const auto& v : ad[u]) { 
    if (v == p || inPath[v]) continue;
    best.push_back(f[v]);
  }
  sort(best.begin(), best.end(), greater<>());
  f[u] = best.size() + best[1] - 2;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> t >> m;
  for (int i = 1; i < n; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  vector<pair<int, int>> value;
  { // build value
    dfs(m);
    reverse(path.begin(), path.end());
    path.pop_back();
    
    int it = 0;
    for (const auto& u : path) {
      it += 1;

      sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
        return f[a] > f[b];
      });

      for (const auto& v : ad[u]) { 
        if (!inPath[v]) value.push_back({f[v], it});
      }
    }

    for (int i = 0; i < (int)value.size(); ++i)
      value[i].first += value.size() - i;
  }

  auto chk = [&](int mid) { 
    int it = 0;
    for (const auto& [w, num] : value) { 
      if (it + w > mid) { 
        if (it >= num) return false;
        it += 1;
      }
    }
    return it <= mid;
  };

  int l = 0, r = 2 * n, answer = 0;
  while (l <= r) { 
    int mid = (l + r) >> 1;
    if (chk(mid)) r = (answer = mid) - 1;
    else l = mid + 1;
  }

  cout << answer << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35