oj.uz

Submission #909416

# Submission time Handle Problem Language Result Execution time Memory
909416 2024-01-17T08:00:08 Z rxlfd314 Highway Tolls (IOI18_highway) C++17
0 / 100
 65 ms 6740 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

void find_pair(int N, vt<int> U, vt<int> V, int A, int B) {
  const int M = size(U);
  vt<ari2> adj[N];
  FOR(i, 0, M-1) {
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  ll C = ask(vt<int>(M));
  vt<int> poss;
  FOR(b, 0, 31 - __builtin_clz(N)) {
    vt<int> v(M);
    FOR(i, 0, N-1)
      if (i & 1 << b) {
        poss.push_back(i);
        for (auto [_, j] : adj[i])
          v[j] = 1;
      }
    ll X = ask(v);
    int a = (X - C) / (B - A);
    if (a & 1)
      break;
    poss.clear();
  }
  int lo = 0, hi = size(poss) - 1;
  while (lo < hi) {
    int mid = lo + hi >> 1;
    vt<int> v(M);
    FOR(ii, 0, mid) {
      int i = poss[ii];
      for (auto [_, j] : adj[i])
        v[j] = 1;
    }
    ll X = ask(v);
    int a = (X - C) / (B - A);
    if (a & 1)
      hi = mid;
    else
      lo = mid + 1;
  }
  int ep = poss[lo];
  poss.clear();
  int par[N];
  function<void(int, int, int)> dfs = [&](int i, int p, int d) {
    if (d == C / A) {
      poss.push_back(i);
      return;
    }
    for (auto [j, ei] : adj[i])
      if (j != p) {
        par[j] = ei;
        dfs(j, i, d + 1);
      }
  };
  dfs(ep, ep, 0);
  lo = 0, hi = size(poss) - 1;
  while (lo < hi) {
    int mid = lo + hi >> 1;
    vt<int> v(M);
    FOR(ii, 0, mid) {
      int i = poss[ii];
      v[par[i]] = 1;
    }
    if (ask(v) != C)
      hi = mid;
    else
      lo = mid + 1;
  }
  answer(ep, poss[lo]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
highway.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = lo + hi >> 1;
      |               ~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 440 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 516 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 9 ms 1268 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 Correct 1 ms 512 KB Output is correct
2 Correct 9 ms 1428 KB Output is correct
3 Incorrect 65 ms 6740 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1348 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 1368 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -