oj.uz

Submission #35900

# Submission time Handle Problem Language Result Execution time Memory
35900 2017-12-02T07:15:57 Z funcsr Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 2066 ms 86116 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], 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 = 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;
  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

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:55:7: note: in expansion of macro 'rep'
       rep(i, V[v].size()) {
       ^
mousetrap.cpp:56: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 16 ms 53776 KB Output is correct
3 Correct 23 ms 53776 KB Output is correct
4 Correct 13 ms 53776 KB Output is correct
5 Correct 9 ms 53776 KB Output is correct
6 Correct 13 ms 53776 KB Output is correct
7 Correct 9 ms 53776 KB Output is correct
8 Correct 16 ms 53776 KB Output is correct
9 Correct 9 ms 53776 KB Output is correct
10 Correct 9 ms 53776 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 85060 KB Output is correct
2 Correct 969 ms 81892 KB Output is correct
3 Correct 2066 ms 86116 KB Output is correct
4 Correct 913 ms 70012 KB Output is correct
5 Correct 2036 ms 86116 KB Output is correct
6 Correct 1989 ms 86116 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53776 KB Output is correct
2 Correct 16 ms 53776 KB Output is correct
3 Correct 23 ms 53776 KB Output is correct
4 Correct 13 ms 53776 KB Output is correct
5 Correct 9 ms 53776 KB Output is correct
6 Correct 13 ms 53776 KB Output is correct
7 Correct 9 ms 53776 KB Output is correct
8 Correct 16 ms 53776 KB Output is correct
9 Correct 9 ms 53776 KB Output is correct
10 Correct 9 ms 53776 KB Output is correct
11 Correct 16 ms 53776 KB Output is correct
12 Correct 16 ms 53776 KB Output is correct
13 Correct 19 ms 53776 KB Output is correct
14 Correct 13 ms 53776 KB Output is correct
15 Correct 9 ms 53776 KB Output is correct
16 Correct 13 ms 53776 KB Output is correct
17 Incorrect 23 ms 53776 KB Output isn't correct
18 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 16 ms 53776 KB Output is correct
3 Correct 23 ms 53776 KB Output is correct
4 Correct 13 ms 53776 KB Output is correct
5 Correct 9 ms 53776 KB Output is correct
6 Correct 13 ms 53776 KB Output is correct
7 Correct 9 ms 53776 KB Output is correct
8 Correct 16 ms 53776 KB Output is correct
9 Correct 9 ms 53776 KB Output is correct
10 Correct 9 ms 53776 KB Output is correct
11 Correct 1069 ms 85060 KB Output is correct
12 Correct 969 ms 81892 KB Output is correct
13 Correct 2066 ms 86116 KB Output is correct
14 Correct 913 ms 70012 KB Output is correct
15 Correct 2036 ms 86116 KB Output is correct
16 Correct 1989 ms 86116 KB Output is correct
17 Correct 16 ms 53776 KB Output is correct
18 Correct 16 ms 53776 KB Output is correct
19 Correct 19 ms 53776 KB Output is correct
20 Correct 13 ms 53776 KB Output is correct
21 Correct 9 ms 53776 KB Output is correct
22 Correct 13 ms 53776 KB Output is correct
23 Incorrect 23 ms 53776 KB Output isn't correct
24 Halted 0 ms 0 KB -