oj.uz

Submission #1036468

# Submission time Handle Problem Language Result Execution time Memory
1036468 2024-07-27T12:00:37 Z abczz Highway Tolls (IOI18_highway) C++17
0 / 100
 12 ms 3740 KB 
#include "highway.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long

using namespace std;

ll l, r, mid, a, b, s, q, rt, P[90000], E[90000];
bool visited[90000];
vector <ll> X;
vector <array<ll, 2> > adj[90000];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  ll M = U.size();
  queue <ll> Q;
  for (int i=0; i<M; ++i) {
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  vector <int> W(M), Z(M);
  for (int i=0; i<M; ++i) W[i] = 0, Z[i] = 1;
  s = ask(W);
  l = 0, r = N-1;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = 0;
    for (int i=0; i<=mid; ++i) {
      for (auto [u, x] : adj[i]) W[x] = 1;
    }
    q = ask(W);
    if (q > s) r = mid;
    else l = mid+1;
  }
  rt = l;
  Q.push(rt);
  visited[rt] = 1;
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    X.push_back(u);
    for (auto [v, x] : adj[u]) {
      if (!visited[v] && v >= rt) {
        Z[x] = 0, visited[v] = 1, E[v] = x, P[v] = u;
        Q.push(v);
      }
    }
  }
  reverse(X.begin(), X.end());
  X.pop_back();
  l = 0, r = X.size()-1;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = Z[i];
    for (int i=mid; i>=0; --i) {
      if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
    }
    q = ask(W);
    if (q > s) r = mid;
    else l = mid+1;
  }
  a = l;
  l = a+1, r = X.size();
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = Z[i];
    for (int i=mid; i>=0; --i) {
      if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
    }
    q = ask(W);
    if (q > s+B-A) r = mid;
    else l = mid+1;
  }
  if (l == (ll)X.size()) answer(rt, X[a]);
  else answer(X[a], X[l]);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 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 3 ms 2648 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 3496 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 2648 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 12 ms 3740 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 Correct 11 ms 3668 KB Output is correct
2 Incorrect 12 ms 3672 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -