oj.uz

Submission #993669

# Submission time Handle Problem Language Result Execution time Memory
993669 2024-06-06T09:53:05 Z poqmen Highway Tolls (IOI18_highway) C++14
18 / 100
 199 ms 10668 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<int>> {
    vector<int> par(n, -1);
    vector<bool> visited(n, false);
    vector<int> bfs_ord;
    vector<int> in(n, INT_MAX);
    queue<int> q;
    q.push(node);
    par[node] = -1;
    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;
        par[v] = top;
        q.push(v);
      }
    }
    return {bfs_ord, in, par};
  };
  // 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, par] = 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:62:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     auto [bfs_ord, in, par] = bfs(root);
      |          ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 600 KB Output is correct
2 Correct 11 ms 1368 KB Output is correct
3 Correct 131 ms 9524 KB Output is correct
4 Correct 128 ms 9532 KB Output is correct
5 Correct 143 ms 9560 KB Output is correct
6 Correct 115 ms 9488 KB Output is correct
7 Correct 119 ms 9592 KB Output is correct
8 Correct 124 ms 9536 KB Output is correct
9 Correct 110 ms 9576 KB Output is correct
10 Correct 124 ms 9548 KB Output is correct
11 Correct 129 ms 9436 KB Output is correct
12 Correct 137 ms 9416 KB Output is correct
13 Correct 122 ms 9648 KB Output is correct
14 Correct 141 ms 9700 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1444 KB Output is correct
2 Correct 18 ms 2444 KB Output is correct
3 Correct 26 ms 3180 KB Output is correct
4 Correct 90 ms 9068 KB Output is correct
5 Correct 83 ms 9040 KB Output is correct
6 Correct 88 ms 9280 KB Output is correct
7 Correct 79 ms 8624 KB Output is correct
8 Correct 86 ms 9104 KB Output is correct
9 Correct 82 ms 8776 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 11 ms 1460 KB Output is correct
3 Correct 97 ms 7268 KB Output is correct
4 Correct 107 ms 8888 KB Output is correct
5 Correct 103 ms 9208 KB Output is correct
6 Correct 99 ms 8892 KB Output is correct
7 Correct 105 ms 9080 KB Output is correct
8 Correct 101 ms 8920 KB Output is correct
9 Correct 139 ms 9324 KB Output is correct
10 Correct 139 ms 9752 KB Output is correct
11 Correct 113 ms 8776 KB Output is correct
12 Correct 138 ms 9456 KB Output is correct
13 Correct 135 ms 9168 KB Output is correct
14 Correct 128 ms 9104 KB Output is correct
15 Correct 114 ms 9700 KB Output is correct
16 Correct 102 ms 8884 KB Output is correct
17 Correct 151 ms 9096 KB Output is correct
18 Correct 107 ms 8768 KB Output is correct
19 Correct 98 ms 8556 KB Output is correct
20 Correct 89 ms 8616 KB Output is correct
21 Incorrect 116 ms 9692 KB Output is incorrect: {s, t} is wrong.
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1364 KB Output is correct
2 Correct 15 ms 1756 KB Output is correct
3 Correct 135 ms 9736 KB Output is correct
4 Correct 160 ms 10564 KB Output is correct
5 Correct 182 ms 10460 KB Output is correct
6 Correct 181 ms 10460 KB Output is correct
7 Correct 198 ms 10440 KB Output is correct
8 Correct 173 ms 10480 KB Output is correct
9 Correct 135 ms 6428 KB Output is correct
10 Incorrect 137 ms 6148 KB Output is incorrect: {s, t} is wrong.
11 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1368 KB Output is correct
2 Correct 14 ms 1368 KB Output is correct
3 Correct 132 ms 9884 KB Output is correct
4 Correct 151 ms 9820 KB Output is correct
5 Correct 170 ms 9860 KB Output is correct
6 Partially correct 185 ms 10492 KB Output is partially correct
7 Correct 124 ms 9924 KB Output is correct
8 Correct 135 ms 9896 KB Output is correct
9 Partially correct 183 ms 10216 KB Output is partially correct
10 Partially correct 176 ms 10540 KB Output is partially correct
11 Correct 199 ms 10668 KB Output is correct
12 Correct 188 ms 10636 KB Output is correct
13 Correct 131 ms 6752 KB Output is correct
14 Correct 154 ms 6696 KB Output is correct
15 Incorrect 167 ms 6884 KB Output is incorrect: {s, t} is wrong.
16 Halted 0 ms 0 KB -