oj.uz

Submission #1081788

# Submission time Handle Problem Language Result Execution time Memory
1081788 2024-08-30T10:48:42 Z erray Highway Tolls (IOI18_highway) C++17
23 / 100
 178 ms 10460 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi18_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename F = function<bool(const int&)>>
int find_first(int l, int r, F good) {
  ++r;
  int bad = r;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (!good(mid)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return (l == bad ? -1 : l);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  vector<vector<int>> g(N);
  for (int i = 0; i < M; ++i) {
    g[U[i]].push_back(i);
    g[V[i]].push_back(i);
  }
  /*
  for (int j = 0; j < 50; ++j) {
    std::vector<int> w(M);
    for (int i = 0; i < M; ++i) {
      w[i] = 0;
    }
    long long toll = ask(w);
  }
  answer(0, N - 1);
  */
  int64_t small = ask(vector<int>(M, 0));
  int on_path = find_first(0, N - 1, [&](int m) {
    vector<int> w(M, 0);
    for (int i = 0; i <= m; ++i) {
      for (auto id : g[i]) w[id] = 1;
    }
    int g = ask(w);
    return g != small;
  });
  assert(on_path != -1);
  debug(on_path);
  //you can predetermine if it's S or T but ignore it for now 
  vector<int> que;
  vector<bool> vis(N);
  vector<int> par(N, -1);
  vis[on_path] = true;
  que.push_back(on_path);
  vector<int> start_w(M, 1);
  for (int it = 0; it < int(que.size()); ++it) {
    int v = que[it];
    for (auto id : g[v]) {
      int u = v ^ V[id] ^ U[id];
      if (!vis[u]) {
        vis[u] = true;
        start_w[id] = 0;
        par[u] = v;
        vis[u] = true;
        que.push_back(u);
      }
    }
  }
  auto ord = que;
  reverse(ord.begin(), ord.end());
  int S = ord[find_first(0, N - 2, [&](int m) {
    auto w = start_w;
    for (int i = 0; i <= m; ++i) {
      for (auto id : g[ord[i]]) w[id] = 1;
    }
    int g = ask(w);
    return g != small;
  })];
  debug(S);
  vector<bool> rem(N);
  {
    int v = S;
    while (v != -1) {
      rem[v] = true;
      v = par[v];
    }
  }
  {
    vector<int> new_ord;
    for (auto v : ord) {
      if (!rem[v]) {
        new_ord.push_back(v);
      }
    }
    swap(ord, new_ord);
  }
  debug(ord);
  int Q_ind = find_first(0, int(ord.size()) - 1, [&](int m) {
    auto w = start_w;
    for (int i = 0; i <= m; ++i) {
      for (auto id : g[ord[i]]) w[id] = 1;
    }
    int g = ask(w);
    return g != small;
  });
  debug(Q_ind);
  if (Q_ind == -1) {
    answer(S, on_path);
  } else {
    answer(S, ord[Q_ind]);
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1440 KB Output is correct
3 Correct 129 ms 9168 KB Output is correct
4 Correct 108 ms 9176 KB Output is correct
5 Correct 106 ms 9176 KB Output is correct
6 Correct 106 ms 9160 KB Output is correct
7 Correct 113 ms 9176 KB Output is correct
8 Correct 126 ms 9184 KB Output is correct
9 Correct 126 ms 9316 KB Output is correct
10 Correct 108 ms 9180 KB Output is correct
11 Correct 102 ms 9048 KB Output is correct
12 Correct 109 ms 9028 KB Output is correct
13 Correct 109 ms 9040 KB Output is correct
14 Incorrect 82 ms 9012 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 14 ms 2444 KB Output is correct
3 Correct 23 ms 3312 KB Output is correct
4 Correct 69 ms 9004 KB Output is correct
5 Correct 75 ms 9068 KB Output is correct
6 Correct 68 ms 8548 KB Output is correct
7 Correct 74 ms 9076 KB Output is correct
8 Correct 90 ms 8692 KB Output is correct
9 Incorrect 63 ms 8396 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 11 ms 1436 KB Output is correct
3 Correct 93 ms 7112 KB Output is correct
4 Correct 133 ms 9176 KB Output is correct
5 Correct 115 ms 9180 KB Output is correct
6 Correct 120 ms 9168 KB Output is correct
7 Correct 113 ms 9180 KB Output is correct
8 Correct 127 ms 9168 KB Output is correct
9 Incorrect 94 ms 9168 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1452 KB Output is correct
2 Correct 12 ms 1248 KB Output is correct
3 Correct 119 ms 9404 KB Output is correct
4 Correct 140 ms 9860 KB Output is correct
5 Correct 157 ms 10156 KB Output is correct
6 Correct 159 ms 10460 KB Output is correct
7 Correct 156 ms 10132 KB Output is correct
8 Correct 162 ms 10336 KB Output is correct
9 Correct 108 ms 6480 KB Output is correct
10 Correct 133 ms 6676 KB Output is correct
11 Correct 111 ms 7436 KB Output is correct
12 Correct 160 ms 9056 KB Output is correct
13 Correct 155 ms 9564 KB Output is correct
14 Correct 154 ms 9992 KB Output is correct
15 Correct 153 ms 9996 KB Output is correct
16 Correct 132 ms 7780 KB Output is correct
17 Correct 105 ms 9516 KB Output is correct
18 Correct 98 ms 9564 KB Output is correct
19 Correct 90 ms 9548 KB Output is correct
20 Correct 94 ms 9852 KB Output is correct
21 Correct 164 ms 10084 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1368 KB Output is correct
2 Correct 12 ms 1484 KB Output is correct
3 Partially correct 126 ms 9420 KB Output is partially correct
4 Partially correct 133 ms 9516 KB Output is partially correct
5 Correct 129 ms 9640 KB Output is correct
6 Correct 156 ms 10144 KB Output is correct
7 Partially correct 130 ms 9416 KB Output is partially correct
8 Correct 135 ms 9524 KB Output is correct
9 Partially correct 135 ms 9620 KB Output is partially correct
10 Correct 153 ms 10144 KB Output is correct
11 Correct 178 ms 10436 KB Output is correct
12 Partially correct 150 ms 10216 KB Output is partially correct
13 Correct 115 ms 7464 KB Output is correct
14 Correct 100 ms 6680 KB Output is correct
15 Correct 118 ms 7448 KB Output is correct
16 Correct 124 ms 6728 KB Output is correct
17 Correct 111 ms 7460 KB Output is correct
18 Correct 134 ms 7004 KB Output is correct
19 Correct 156 ms 9012 KB Output is correct
20 Correct 149 ms 9468 KB Output is correct
21 Partially correct 152 ms 10004 KB Output is partially correct
22 Partially correct 157 ms 9984 KB Output is partially correct
23 Partially correct 145 ms 10004 KB Output is partially correct
24 Partially correct 148 ms 10052 KB Output is partially correct
25 Correct 147 ms 9980 KB Output is correct
26 Correct 145 ms 10000 KB Output is correct
27 Correct 99 ms 9572 KB Output is correct
28 Partially correct 108 ms 9504 KB Output is partially correct
29 Partially correct 99 ms 9692 KB Output is partially correct
30 Incorrect 80 ms 9564 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -