oj.uz

Submission #909535

# Submission time Handle Problem Language Result Execution time Memory
909535 2024-01-17T08:48:01 Z rxlfd314 Highway Tolls (IOI18_highway) C++17
12 / 100
 252 ms 262144 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> nodes[2];
  function<void(int, int, bool)> dfs = [&](int i, int p, bool c) {
    nodes[c].push_back(i);
    for (auto [j, _] : adj[i])
      if (j != p)
        dfs(j, i, !c);
  };
  dfs(0, 0, 0);
  vt<int> poss;
  if (C / A & 1) {
    poss = nodes[0];
    goto jail;
  }
  FOR(_, 0, 1) {
    FOR(b, 0, 31 - __builtin_clz(size(nodes[0]))) {
      vt<int> v(M);
      FOR(ii, 0, size(nodes[0])-1)
        if (ii & 1 << b) {
          int i = nodes[0][ii];
          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();
    }
    if (size(poss))
      break;
  }
  jail:;
  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)> dfs2 = [&](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;
        dfs2(j, i, d + 1);
      }
  };
  dfs2(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:58:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
highway.cpp:89:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     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 1 ms 440 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 1 ms 692 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 440 KB Output is correct
12 Correct 1 ms 436 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 9 ms 1468 KB Output is correct
3 Correct 133 ms 8952 KB Output is correct
4 Correct 100 ms 9028 KB Output is correct
5 Correct 96 ms 8732 KB Output is correct
6 Correct 109 ms 9352 KB Output is correct
7 Correct 95 ms 8740 KB Output is correct
8 Correct 117 ms 8720 KB Output is correct
9 Correct 107 ms 8960 KB Output is correct
10 Correct 116 ms 8972 KB Output is correct
11 Correct 93 ms 9784 KB Output is correct
12 Correct 125 ms 10516 KB Output is correct
13 Correct 105 ms 10288 KB Output is correct
14 Correct 80 ms 9092 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2036 KB Output is correct
2 Correct 14 ms 3668 KB Output is correct
3 Correct 24 ms 5232 KB Output is correct
4 Correct 89 ms 14864 KB Output is correct
5 Correct 81 ms 15364 KB Output is correct
6 Correct 73 ms 15364 KB Output is correct
7 Correct 65 ms 14864 KB Output is correct
8 Correct 72 ms 14868 KB Output is correct
9 Incorrect 80 ms 15348 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 10 ms 1528 KB Output is correct
3 Correct 60 ms 7236 KB Output is correct
4 Correct 111 ms 8968 KB Output is correct
5 Correct 81 ms 8720 KB Output is correct
6 Incorrect 123 ms 9440 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -