oj.uz

Submission #993664

# Submission time Handle Problem Language Result Execution time Memory
993664 2024-06-06T09:45:44 Z poqmen Highway Tolls (IOI18_highway) C++14
0 / 100
 9 ms 1368 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[node]) {
        if (visited[v]) continue;
        if (v < il) continue;
        visited[v] = true;
        par[v] = node;
        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;
      }
    }
    return 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1112 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1280 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1368 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -