oj.uz

Submission #909422

# Submission time Handle Problem Language Result Execution time Memory
909422 2024-01-17T08:04:15 Z rxlfd314 Highway Tolls (IOI18_highway) C++17
12 / 100
 156 ms 9360 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 = 0;
  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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 8 ms 1340 KB Output is correct
3 Correct 96 ms 8684 KB Output is correct
4 Correct 103 ms 8692 KB Output is correct
5 Correct 100 ms 8688 KB Output is correct
6 Correct 156 ms 9080 KB Output is correct
7 Correct 98 ms 8812 KB Output is correct
8 Correct 109 ms 8692 KB Output is correct
9 Correct 76 ms 8688 KB Output is correct
10 Correct 120 ms 8460 KB Output is correct
11 Correct 133 ms 9264 KB Output is correct
12 Correct 87 ms 9016 KB Output is correct
13 Correct 74 ms 8844 KB Output is correct
14 Correct 90 ms 9360 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1324 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 508 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 21 ms 2044 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 19 ms 1456 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -