oj.uz

Submission #993672

# Submission time Handle Problem Language Result Execution time Memory
993672 2024-06-06T09:56:06 Z poqmen Highway Tolls (IOI18_highway) C++14
90 / 100
 199 ms 9972 KB 
#include "highway.h"

#include <bits/stdc++.h>
using namespace std;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
  vector<vector<int>> adj(n);
  int m = u.size();
  for (int i = 0; i < m; ++i)
    adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
  // ShortestPathDAG - {(u, v) | is_in_subgraph(u, v)} = Connected -> False
  // Disconnected -> True
  vector<int> hl(m, 0);
  int64_t req_d = ask(hl);
  auto is_shortestpathdag_cut =
      [&](function<bool(int, int)> is_in_cut) -> bool {
    for (int i = 0; i < m; ++i) {
      hl[i] = is_in_cut(u[i], v[i]);
    }
    return ask(hl) != req_d;
  };
  // find a cut in ShortestPathDAG w. smallest max element
  // i=il -> not cut, i=ih -> cut
  int il = 0, ih = n;
  while (il + 1 < ih) {
    int im = (il + ih) / 2;
    if (is_shortestpathdag_cut(
            [&](int u, int v) { return u < im || v < im; })) {
      ih = im;
    } else {
      il = im;
    }
  }
  // now remove all nodes < il
  // il is articulation point in ShortestPathDAG
  auto bfs = [&](int node) -> tuple<vector<int>, vector<int>> {
    vector<bool> visited(n, false);
    vector<int> bfs_ord;
    vector<int> in(n, INT_MAX);
    queue<int> q;
    q.push(node);
    visited[node] = true;
    int t = 0;
    while (!q.empty()) {
      auto top = q.front();
      q.pop();
      in[top] = t++;
      bfs_ord.push_back(top);
      for (auto v : adj[top]) {
        if (visited[v]) continue;
        if (v < il) continue;
        visited[v] = true;
        q.push(v);
      }
    }
    return {bfs_ord, in};
  };
  // ShortestPathDAG & BFSTree(il) has unique shortest path from s to t
  // node s and t are in different children of il
  auto find_end = [&](int root) {
    auto [bfs_ord, in] = bfs(root);
    // tl -> cut, th -> not cut
    int tl = 0, th = bfs_ord.size();
    while (tl + 1 < th) {
      int tm = (tl + th) / 2;
      if (is_shortestpathdag_cut([&](int u, int v) {
            if (u < il || v < il) return true;
            if (in[u] >= tm || in[v] >= tm) return true;
            return false;
          })) {
        tl = tm;
      } else {
        th = tm;
      }
    }
    // in tl, adding tl makes it uncut
    return bfs_ord[tl];
  };
  // tl -> cut, th -> not cut
  // graph @ tl + tl = th
  // tl = s
  int s = find_end(il);
  int t = find_end(s);
  answer(s, t);
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message

highway.cpp: In lambda function:
highway.cpp:60:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     auto [bfs_ord, in] = bfs(root);
      |          ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 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 0 ms 344 KB Output is correct
8 Correct 0 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 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1392 KB Output is correct
3 Correct 136 ms 9108 KB Output is correct
4 Correct 127 ms 8840 KB Output is correct
5 Correct 134 ms 8836 KB Output is correct
6 Correct 113 ms 8824 KB Output is correct
7 Correct 143 ms 8844 KB Output is correct
8 Correct 125 ms 9092 KB Output is correct
9 Correct 114 ms 8848 KB Output is correct
10 Correct 118 ms 8840 KB Output is correct
11 Correct 114 ms 8720 KB Output is correct
12 Correct 128 ms 8708 KB Output is correct
13 Correct 145 ms 9044 KB Output is correct
14 Correct 137 ms 8684 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1372 KB Output is correct
2 Correct 18 ms 2260 KB Output is correct
3 Correct 25 ms 3104 KB Output is correct
4 Correct 90 ms 8352 KB Output is correct
5 Correct 89 ms 8388 KB Output is correct
6 Correct 90 ms 8568 KB Output is correct
7 Correct 74 ms 7896 KB Output is correct
8 Correct 82 ms 8352 KB Output is correct
9 Correct 81 ms 8076 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 15 ms 1200 KB Output is correct
3 Correct 81 ms 6720 KB Output is correct
4 Correct 94 ms 8188 KB Output is correct
5 Correct 105 ms 8780 KB Output is correct
6 Correct 92 ms 7944 KB Output is correct
7 Correct 104 ms 8380 KB Output is correct
8 Correct 104 ms 8184 KB Output is correct
9 Correct 127 ms 8712 KB Output is correct
10 Correct 128 ms 8848 KB Output is correct
11 Correct 112 ms 8064 KB Output is correct
12 Correct 129 ms 8580 KB Output is correct
13 Correct 149 ms 8860 KB Output is correct
14 Correct 125 ms 8588 KB Output is correct
15 Correct 104 ms 8968 KB Output is correct
16 Correct 106 ms 8168 KB Output is correct
17 Correct 134 ms 8448 KB Output is correct
18 Correct 109 ms 8040 KB Output is correct
19 Correct 81 ms 7908 KB Output is correct
20 Correct 106 ms 7904 KB Output is correct
21 Correct 110 ms 8984 KB Output is correct
22 Correct 118 ms 8804 KB Output is correct
23 Correct 125 ms 9244 KB Output is correct
24 Correct 98 ms 9208 KB Output is correct
25 Correct 118 ms 8788 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1424 KB Output is correct
2 Correct 14 ms 1244 KB Output is correct
3 Correct 126 ms 9044 KB Output is correct
4 Correct 149 ms 9180 KB Output is correct
5 Correct 174 ms 9760 KB Output is correct
6 Correct 191 ms 9712 KB Output is correct
7 Correct 176 ms 9748 KB Output is correct
8 Correct 168 ms 9792 KB Output is correct
9 Correct 134 ms 6192 KB Output is correct
10 Correct 129 ms 5924 KB Output is correct
11 Correct 121 ms 6356 KB Output is correct
12 Correct 165 ms 8712 KB Output is correct
13 Correct 199 ms 9288 KB Output is correct
14 Correct 173 ms 9600 KB Output is correct
15 Correct 176 ms 9616 KB Output is correct
16 Correct 171 ms 7028 KB Output is correct
17 Correct 123 ms 9316 KB Output is correct
18 Correct 124 ms 9324 KB Output is correct
19 Correct 121 ms 9588 KB Output is correct
20 Correct 117 ms 8980 KB Output is correct
21 Correct 159 ms 9740 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1368 KB Output is correct
2 Correct 13 ms 1368 KB Output is correct
3 Correct 120 ms 8964 KB Output is correct
4 Partially correct 158 ms 9108 KB Output is partially correct
5 Correct 159 ms 9136 KB Output is correct
6 Partially correct 181 ms 9796 KB Output is partially correct
7 Correct 121 ms 8996 KB Output is correct
8 Partially correct 145 ms 9452 KB Output is partially correct
9 Correct 146 ms 9316 KB Output is correct
10 Correct 167 ms 9972 KB Output is correct
11 Correct 180 ms 9736 KB Output is correct
12 Correct 181 ms 9832 KB Output is correct
13 Correct 136 ms 6420 KB Output is correct
14 Correct 152 ms 6144 KB Output is correct
15 Correct 151 ms 6548 KB Output is correct
16 Correct 159 ms 6088 KB Output is correct
17 Correct 119 ms 6308 KB Output is correct
18 Correct 160 ms 6144 KB Output is correct
19 Correct 164 ms 8696 KB Output is correct
20 Correct 158 ms 9152 KB Output is correct
21 Partially correct 176 ms 9552 KB Output is partially correct
22 Correct 173 ms 9584 KB Output is correct
23 Partially correct 164 ms 9664 KB Output is partially correct
24 Partially correct 195 ms 9612 KB Output is partially correct
25 Correct 162 ms 9256 KB Output is correct
26 Partially correct 172 ms 9780 KB Output is partially correct
27 Correct 121 ms 9332 KB Output is correct
28 Correct 124 ms 9172 KB Output is correct
29 Correct 124 ms 9024 KB Output is correct
30 Correct 124 ms 8816 KB Output is correct
31 Correct 122 ms 9256 KB Output is correct
32 Correct 132 ms 8804 KB Output is correct
33 Correct 134 ms 9348 KB Output is correct
34 Correct 133 ms 9440 KB Output is correct
35 Correct 120 ms 9484 KB Output is correct
36 Correct 125 ms 9120 KB Output is correct
37 Correct 120 ms 8984 KB Output is correct
38 Correct 135 ms 9020 KB Output is correct
39 Correct 163 ms 9716 KB Output is correct
40 Partially correct 171 ms 9968 KB Output is partially correct
41 Partially correct 156 ms 9748 KB Output is partially correct
42 Correct 158 ms 9728 KB Output is correct