oj.uz

답안 #35895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35895 2017-12-02T06:51:29 Z funcsr Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 1002 ms 85060 KB 
#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];

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

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;
  path.pb(u);
  while (true) {
    for (int t : G[u]) if (t != par && sub[t]) {
      par = u, u = t;
      break;
    }
    if (u == T) break;
    path.pb(u);
  }
  rep(i, N) if (sub[i] && i != T) {
    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

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:57:7: note: in expansion of macro 'rep'
       rep(i, V[v].size()) {
       ^
mousetrap.cpp:59:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         int next = (i+1 == V[v].size()) ?0:V[v][i+1];
                         ^
mousetrap.cpp:58:13: warning: unused variable 't' [-Wunused-variable]
         int t = V[v][i];
             ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 53776 KB Output is correct
2 Correct 16 ms 53776 KB Output is correct
3 Correct 13 ms 53776 KB Output is correct
4 Correct 19 ms 53776 KB Output is correct
5 Incorrect 9 ms 53776 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1002 ms 85060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 53776 KB Output is correct
2 Correct 16 ms 53776 KB Output is correct
3 Correct 13 ms 53776 KB Output is correct
4 Correct 19 ms 53776 KB Output is correct
5 Incorrect 9 ms 53776 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 53776 KB Output is correct
2 Correct 16 ms 53776 KB Output is correct
3 Correct 13 ms 53776 KB Output is correct
4 Correct 19 ms 53776 KB Output is correct
5 Incorrect 9 ms 53776 KB Output isn't correct
6 Halted 0 ms 0 KB -