oj.uz

Submission #823366

# Submission time Handle Problem Language Result Execution time Memory
823366 2023-08-12T11:56:14 Z KoD Highway Tolls (IOI18_highway) C++17
0 / 100
 17 ms 1160 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

template <class F> int binary_search(int ok, int ng, int md, const F& f) {
  while (abs(ok - ng) > 1) {
    (f(md) ? ok : ng) = md;
    md = (ok + ng) / 2;
  }
  return ok;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  const int M = (int)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);
  }
  vector<char> dead(N);
  const auto bfs_order = [&](int src) {
    vector<int> ret;
    vector<char> done(N);
    queue<int> que;
    ret.reserve(N);
    const auto push = [&](int u) {
      if (!dead[u] && !done[u]) {
        done[u] = true;
        ret.push_back(u);
        que.push(u);
      }
    };
    push(src);
    while (!que.empty()) {
      const int u = que.front();
      que.pop();
      for (const int e : G[u]) {
        push(u ^ U[e] ^ V[e]);
      }
    }
    return ret;
  };
  const long long best = ask(vector(M, 0));
  const int P = binary_search(0, N, N / 3, [&](int thres) {
    vector<int> w(M);
    for (int i = 0; i < thres; ++i) {
      for (const int e : G[i]) w[e] = 1;
    }
    return ask(w) == best;
  });
  for (int i = 0; i < P; ++i) dead[i] = true;
  const int S = [&] {
    const auto ord = bfs_order(P);
    const int n = (int)ord.size();
    const int k = binary_search(n, 0, 2 * n / 3, [&](int thres) {
      vector<int> w(M);
      for (int i = thres; i < n; ++i) {
        for (const int e : G[i]) w[e] = 1;
      }
      for (int i = 0; i < N; ++i) {
        if (dead[i]) {
          for (const int e : G[i]) w[e] = 1;
        }
      }
      return ask(w) == best;
    });
    for (int i = k; i < n; ++i) dead[ord[i]] = true;
    return ord[k - 1];
  }();
  const int T = [&] {
    const auto ord = bfs_order(S);
    const int n = (int)ord.size();
    const int k = binary_search(n, 0, 2 * n / 3, [&](int thres) {
      vector<int> w(M);
      for (int i = thres; i < n; ++i) {
        for (const int e : G[i]) w[e] = 1;
      }
      for (int i = 0; i < N; ++i) {
        if (dead[i]) {
          for (const int e : G[i]) w[e] = 1;
        }
      }
      return ask(w) == best;
    });
    for (int i = k; i < n; ++i) dead[ord[i]] = true;
    return ord[k - 1];
  }();
  answer(S, T);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 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 336 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 10 ms 1104 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 336 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 17 ms 1160 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 10 ms 1144 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -