oj.uz

Submission #35902

# Submission time Handle Problem Language Result Execution time Memory
35902 2017-12-02T07:43:16 Z funcsr Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 2103 ms 163056 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 = 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

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.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 85060 KB Output is correct
2 Correct 926 ms 81892 KB Output is correct
3 Correct 2103 ms 86116 KB Output is correct
4 Correct 993 ms 70012 KB Output is correct
5 Correct 2043 ms 86116 KB Output is correct
6 Correct 1983 ms 86116 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 53776 KB Output is correct
2 Correct 13 ms 53776 KB Output is correct
3 Correct 19 ms 53776 KB Output is correct
4 Correct 13 ms 53776 KB Output is correct
5 Correct 13 ms 53776 KB Output is correct
6 Correct 9 ms 53776 KB Output is correct
7 Correct 19 ms 53776 KB Output is correct
8 Correct 16 ms 53776 KB Output is correct
9 Correct 16 ms 53776 KB Output is correct
10 Correct 19 ms 53776 KB Output is correct
11 Correct 13 ms 53776 KB Output is correct
12 Correct 13 ms 53776 KB Output is correct
13 Correct 16 ms 53776 KB Output is correct
14 Correct 16 ms 53776 KB Output is correct
15 Correct 9 ms 53776 KB Output is correct
16 Correct 9 ms 53776 KB Output is correct
17 Correct 13 ms 53776 KB Output is correct
18 Correct 13 ms 53776 KB Output is correct
19 Correct 6 ms 53776 KB Output is correct
20 Correct 16 ms 53776 KB Output is correct
21 Correct 19 ms 53776 KB Output is correct
22 Correct 19 ms 53776 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 53776 KB Output is correct
2 Correct 13 ms 53776 KB Output is correct
3 Correct 19 ms 53776 KB Output is correct
4 Correct 13 ms 53776 KB Output is correct
5 Correct 13 ms 53776 KB Output is correct
6 Correct 9 ms 53776 KB Output is correct
7 Correct 19 ms 53776 KB Output is correct
8 Correct 16 ms 53776 KB Output is correct
9 Correct 16 ms 53776 KB Output is correct
10 Correct 19 ms 53776 KB Output is correct
11 Correct 1119 ms 85060 KB Output is correct
12 Correct 926 ms 81892 KB Output is correct
13 Correct 2103 ms 86116 KB Output is correct
14 Correct 993 ms 70012 KB Output is correct
15 Correct 2043 ms 86116 KB Output is correct
16 Correct 1983 ms 86116 KB Output is correct
17 Correct 13 ms 53776 KB Output is correct
18 Correct 13 ms 53776 KB Output is correct
19 Correct 16 ms 53776 KB Output is correct
20 Correct 16 ms 53776 KB Output is correct
21 Correct 9 ms 53776 KB Output is correct
22 Correct 9 ms 53776 KB Output is correct
23 Correct 13 ms 53776 KB Output is correct
24 Correct 13 ms 53776 KB Output is correct
25 Correct 6 ms 53776 KB Output is correct
26 Correct 16 ms 53776 KB Output is correct
27 Correct 19 ms 53776 KB Output is correct
28 Correct 19 ms 53776 KB Output is correct
29 Correct 6 ms 53776 KB Output is correct
30 Correct 1059 ms 85060 KB Output is correct
31 Correct 986 ms 85060 KB Output is correct
32 Correct 1176 ms 153628 KB Output is correct
33 Correct 1012 ms 163056 KB Output is correct
34 Correct 1976 ms 86116 KB Output is correct
35 Correct 1966 ms 86116 KB Output is correct
36 Correct 1939 ms 95656 KB Output is correct
37 Correct 2016 ms 95660 KB Output is correct
38 Correct 1616 ms 97416 KB Output is correct
39 Correct 1549 ms 97424 KB Output is correct
40 Correct 1623 ms 97284 KB Output is correct