Submission #35902

#	Time	Username	Problem	Language	Result	Execution time	Memory
35902		funcsr	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	2103 ms	163056 KiB

mousetrap

#include <iostream>
#include <vector>
#include <algorithm>
#define pb push_back
#define all(xs) xs.begin(), xs.end()
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;

int N, T, M;
vector<int> G[1000000], V[1000000];
bool sub[1000000];
int R[1000000];

void dfs(int x, int p) {
  sub[x] = x == M;
  for (int t : G[x]) {
    if (t == p) continue;
    dfs(t, x);
    sub[x] |= sub[t];
  }
}

struct Max2 {
  int m1 = -1, m2 = -1;
  void add(int x) {
    if (x > m1) m2 = m1, m1 = x;
    else if (x > m2) m2 = x;
  }
};

int dfs2(int x, int p) {
  Max2 max2;
  int ctr = 0;
  for (int t : G[x]) {
    if (t == p) continue;
    max2.add(dfs2(t, x));
    ctr++;
  }
  if (max2.m2 != -1) ctr += max2.m2;
  return ctr;
}

vector<int> path;
bool solve(int X) {
  //cout<<"solve("<<X<<")\n";
  int all = 0, stock = 0;
  for (int v : path) all += R[v];
  for (int v : path) {
    stock++;
    //cout<<"all="<<all<<"\n";
    bool ok = false;
    if (V[v].empty()) ok = all <= X;
    else if (all+V[v][0] <= X) ok = true; // do nothing
    else {
      int ctr = 0;
      rep(i, V[v].size()) {
        int next = (i+1 == V[v].size())? 0 : V[v][i+1];
        if (stock == 0) return false;
        //cout<<"take "<<V[v][i]<<" (next="<<next<<"): stock="<<stock<<"--\n";
        stock--, ctr++;
        if (all+next <= X) {
          ok = true;
          break;
        }
      }
      all += ctr;
    }
    if (!ok) return false;
    all -= R[v];
  }
  return all <= X;
}

signed main() {
  cin >> N >> T >> M;
  T--, M--;
  if (T == M) {
    cout << 0 << "\n";
    return 0;
  }
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  dfs(T, -1);

  int u = M, par = -1;
  while (true) {
    path.pb(u);
    for (int t : G[u]) if (t != par && sub[t]) {
      par = u, u = t;
      break;
    }
    if (u == T) break;
  }
  for (int i : path) {
    for (int t : G[i]) if (!sub[t]) V[i].pb(dfs2(t, i)), R[i]++;
    sort(all(V[i]), greater<int>());
  }
  //for (int x:path){ cout<<"{"; for (int t:V[x])cout<<t<<","; cout<<"},"; }cout<<"\n";

  int lo = -1, hi = N+2;
  while (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    if (solve(mid)) hi = mid;
    else lo = mid;
  }
  cout << hi << "\n";
  return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'bool solve(int)':
mousetrap.cpp:6:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
mousetrap.cpp:56:7: note: in expansion of macro 'rep'
       rep(i, V[v].size()) {
       ^
mousetrap.cpp:57:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         int next = (i+1 == V[v].size())? 0 : V[v][i+1];
                         ^

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