oj.uz

Submission #296229

# Submission time Handle Problem Language Result Execution time Memory
296229 2020-09-10T12:26:19 Z Bruteforceman Highway Tolls (IOI18_highway) C++11
90 / 100
 374 ms 10608 KB 
#include "bits/stdc++.h"
#include "highway.h"
using namespace std;
const int maxn = 1e5;
vector <int> g[maxn];

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();
  int l, r;
  long long initDist = ask(vector <int> (m, 0));
  l = 0, r = m;
  while(l < r) {
    vector <int> v (m, 0);
    int mid = (l + r + 1) >> 1;
    for(int i = 0; i < mid; i++) {
      v[i] = 1;
    }
    if(ask(v) == initDist) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  vector <int> state (m, 0);
  for(int i = 0; i < l; i++) state[i] = 1;
  vector <int> order;
  queue <int> Q;
  vector <int> dist (n, -1);
  Q.push(U[l]);
  Q.push(V[l]);
  dist[U[l]] = dist[V[l]] = 0;
  for(int i = 0; i < m; i++) {
    if(state[i] == 0) {
      g[U[i]].push_back(V[i]);
      g[V[i]].push_back(U[i]);
    }
  }
  while(not Q.empty()) {
    int x = Q.front();
    Q.pop();
    order.push_back(x);
    for(int i : g[x]) {
      if(dist[i] == -1) {
        dist[i] = dist[x] + 1;
        Q.push(i);
      }
    }
  }
  reverse(order.begin(), order.end());
  auto getEndpoint = [&] (vector <int> order) { 
    int l = 0, r = order.size() - 1;
    while(l < r) {
      int mid = (l + r) >> 1;
      vector <int> v = state;
      vector <int> mark (n, 0);
      for(int i = 0; i <= mid; i++) {
        mark[order[i]] = 1;
      }
      for(int i = 0; i < m; i++) {
        if(mark[U[i]] || mark[V[i]]) {
          v[i] = 1;
        }
      }
      if(ask(v) == initDist) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    return order[l];
  };
  int src = getEndpoint(order);
  Q.push(src);
  dist = vector <int> (n, -1);
  dist[src] = 0;
  order.clear();
  while(not Q.empty()) {
    int x = Q.front();
    Q.pop();
    order.push_back(x);
    for(int i : g[x]) {
      if(dist[i] == -1) {
        dist[i] = 1 + dist[x];
        Q.push(i);
      }
    }
  }
  reverse(order.begin(), order.end());
  int des = getEndpoint(order);
  answer(src, des);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 15 ms 3464 KB Output is correct
3 Correct 194 ms 9084 KB Output is correct
4 Correct 180 ms 9264 KB Output is correct
5 Correct 199 ms 9404 KB Output is correct
6 Correct 156 ms 8960 KB Output is correct
7 Correct 174 ms 8772 KB Output is correct
8 Correct 197 ms 9232 KB Output is correct
9 Correct 181 ms 8768 KB Output is correct
10 Correct 174 ms 9540 KB Output is correct
11 Correct 153 ms 8492 KB Output is correct
12 Correct 202 ms 9072 KB Output is correct
13 Correct 211 ms 9072 KB Output is correct
14 Correct 192 ms 9340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3328 KB Output is correct
2 Correct 28 ms 4060 KB Output is correct
3 Correct 40 ms 3804 KB Output is correct
4 Correct 137 ms 7796 KB Output is correct
5 Correct 127 ms 7940 KB Output is correct
6 Correct 131 ms 8448 KB Output is correct
7 Correct 116 ms 5800 KB Output is correct
8 Correct 129 ms 8120 KB Output is correct
9 Correct 126 ms 6792 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 18 ms 3320 KB Output is correct
3 Correct 136 ms 7820 KB Output is correct
4 Correct 198 ms 9068 KB Output is correct
5 Correct 131 ms 8132 KB Output is correct
6 Correct 132 ms 8364 KB Output is correct
7 Correct 178 ms 8756 KB Output is correct
8 Correct 142 ms 8336 KB Output is correct
9 Correct 210 ms 9296 KB Output is correct
10 Correct 191 ms 8960 KB Output is correct
11 Correct 210 ms 9064 KB Output is correct
12 Correct 201 ms 9024 KB Output is correct
13 Correct 200 ms 8896 KB Output is correct
14 Correct 154 ms 8588 KB Output is correct
15 Correct 147 ms 8280 KB Output is correct
16 Correct 118 ms 7620 KB Output is correct
17 Correct 197 ms 9016 KB Output is correct
18 Correct 216 ms 9096 KB Output is correct
19 Correct 113 ms 8124 KB Output is correct
20 Correct 146 ms 8428 KB Output is correct
21 Correct 137 ms 8176 KB Output is correct
22 Correct 162 ms 6712 KB Output is correct
23 Correct 215 ms 9988 KB Output is correct
24 Correct 162 ms 9560 KB Output is correct
25 Correct 191 ms 9152 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3448 KB Output is correct
2 Correct 20 ms 3448 KB Output is correct
3 Correct 225 ms 9476 KB Output is correct
4 Correct 221 ms 9416 KB Output is correct
5 Correct 246 ms 9860 KB Output is correct
6 Correct 279 ms 10580 KB Output is correct
7 Correct 233 ms 10060 KB Output is correct
8 Correct 322 ms 9928 KB Output is correct
9 Correct 188 ms 6208 KB Output is correct
10 Correct 241 ms 7332 KB Output is correct
11 Correct 244 ms 8008 KB Output is correct
12 Correct 324 ms 9792 KB Output is correct
13 Correct 294 ms 9992 KB Output is correct
14 Correct 326 ms 10272 KB Output is correct
15 Correct 246 ms 10392 KB Output is correct
16 Correct 247 ms 8784 KB Output is correct
17 Correct 216 ms 9900 KB Output is correct
18 Correct 185 ms 8424 KB Output is correct
19 Correct 159 ms 9624 KB Output is correct
20 Correct 142 ms 8852 KB Output is correct
21 Correct 243 ms 10596 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3456 KB Output is correct
2 Correct 25 ms 3448 KB Output is correct
3 Correct 218 ms 9568 KB Output is correct
4 Correct 270 ms 9692 KB Output is correct
5 Partially correct 241 ms 9656 KB Output is partially correct
6 Partially correct 335 ms 10152 KB Output is partially correct
7 Partially correct 278 ms 9448 KB Output is partially correct
8 Partially correct 216 ms 9644 KB Output is partially correct
9 Correct 233 ms 10084 KB Output is correct
10 Correct 301 ms 10268 KB Output is correct
11 Partially correct 310 ms 10364 KB Output is partially correct
12 Partially correct 242 ms 10292 KB Output is partially correct
13 Correct 197 ms 6288 KB Output is correct
14 Correct 229 ms 6112 KB Output is correct
15 Correct 204 ms 8672 KB Output is correct
16 Correct 177 ms 7208 KB Output is correct
17 Correct 301 ms 8048 KB Output is correct
18 Correct 198 ms 7348 KB Output is correct
19 Correct 226 ms 9624 KB Output is correct
20 Correct 308 ms 9940 KB Output is correct
21 Correct 264 ms 10164 KB Output is correct
22 Partially correct 266 ms 10156 KB Output is partially correct
23 Partially correct 290 ms 10212 KB Output is partially correct
24 Partially correct 295 ms 10332 KB Output is partially correct
25 Correct 306 ms 10060 KB Output is correct
26 Partially correct 374 ms 10264 KB Output is partially correct
27 Correct 213 ms 8696 KB Output is correct
28 Correct 193 ms 9284 KB Output is correct
29 Correct 200 ms 10000 KB Output is correct
30 Partially correct 205 ms 9768 KB Output is partially correct
31 Correct 205 ms 9660 KB Output is correct
32 Correct 172 ms 9524 KB Output is correct
33 Partially correct 173 ms 10048 KB Output is partially correct
34 Correct 206 ms 8848 KB Output is correct
35 Correct 207 ms 9428 KB Output is correct
36 Partially correct 192 ms 9628 KB Output is partially correct
37 Correct 233 ms 9548 KB Output is correct
38 Correct 233 ms 9576 KB Output is correct
39 Correct 320 ms 10248 KB Output is correct
40 Correct 311 ms 10364 KB Output is correct
41 Partially correct 294 ms 10600 KB Output is partially correct
42 Correct 314 ms 10608 KB Output is correct