oj.uz

Submission #35898

# Submission time Handle Problem Language Result Execution time Memory
35898 2017-12-02T07:07:37 Z funcsr Mousetrap (CEOI17_mousetrap) C++14
20 / 100
 1029 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, 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 = true;
    else if (all+V[v][0] <= X) ok = true; // do nothing
    else {
      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--;
        if (all+next <= X) {
          ok = true;
          break;
        }
      }
    }
    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;
  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:58: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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53776 KB Output is correct
2 Correct 13 ms 53776 KB Output is correct
3 Correct 13 ms 53776 KB Output is correct
4 Correct 6 ms 53776 KB Output is correct
5 Correct 9 ms 53776 KB Output is correct
6 Correct 6 ms 53776 KB Output is correct
7 Correct 13 ms 53776 KB Output is correct
8 Correct 9 ms 53776 KB Output is correct
9 Correct 6 ms 53776 KB Output is correct
10 Correct 9 ms 53776 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1029 ms 85060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53776 KB Output is correct
2 Correct 13 ms 53776 KB Output is correct
3 Correct 13 ms 53776 KB Output is correct
4 Correct 6 ms 53776 KB Output is correct
5 Correct 9 ms 53776 KB Output is correct
6 Correct 6 ms 53776 KB Output is correct
7 Correct 13 ms 53776 KB Output is correct
8 Correct 9 ms 53776 KB Output is correct
9 Correct 6 ms 53776 KB Output is correct
10 Correct 9 ms 53776 KB Output is correct
11 Incorrect 1029 ms 85060 KB Output isn't correct
12 Halted 0 ms 0 KB -