oj.uz

Submission #1057293

# Submission time Handle Problem Language Result Execution time Memory
1057293 2024-08-13T16:35:31 Z TAhmed33 Highway Tolls (IOI18_highway) C++17
0 / 100
 13 ms 25184 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
int n, m;
map <int, int> ind[MAXN];
vector <int> cc[MAXN];
int dist[MAXN]; 
int in[MAXN], out[MAXN], tt, p[MAXN];
int gg[MAXN];
void dfs (int pos) {
  in[pos] = ++tt; gg[tt] = pos;
  for (auto j : cc[pos]) {
    p[j] = pos;
    dfs(j);
  }
  out[pos] = tt;
}
void find_pair (int N, vector <int> U, vector <int> V, int A, int B) {
  n = N; m = U.size();
  vector <int> x(m, 0);
  ll z = ask(x);
  for (int i = 0; i < m; i++) {
    adj[U[i]].push_back(V[i]);
    adj[V[i]].push_back(U[i]);
    ind[U[i]][V[i]] = ind[V[i]][U[i]] = i;
  }
  int l = 0, r = m - 1, ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    x.assign(m, 0);
    for (int j = 0; j < mid; j++) {
      x[j] = 1;
    }
    if (ask(x) == z) {
      l = mid + 1; ans = mid;
    } else {
      r = mid - 1;
    }
  }
  memset(dist, -1, sizeof(dist));
  queue <int> cur;
  cur.push(U[ans]); cur.push(V[ans]); dist[V[ans]] = 1; dist[U[ans]] = 0;
  cc[U[ans]].push_back(V[ans]);
  vector <int> spec = {ans};
  while (!cur.empty()) {
    auto k = cur.front();
    cur.pop();
    for (auto j : adj[k]) {
      if (dist[j] == -1) {
        dist[j] = dist[k] + 1;
        cc[k].push_back(j);
        cur.push(j); 
        spec.push_back(ind[j][k]);
      }
    }
  }
  x.assign(m, 1);
  p[U[ans]] = -1;
  swap(cc[U[ans]].front(), cc[U[ans]].back());
  dfs(U[ans]);
  l = 2, r = in[V[ans]] - 1; int ans2 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    for (auto i : spec) {
      x[i] = 0;
    }
    for (int j = 2; j <= mid; j++) {
      x[ind[gg[j]][p[gg[j]]]] = 1;
    }
    if (ask(x) != z) {
      r = mid - 1; ans2 = mid;
    } else {
      l = mid + 1;
    }
  }
  if (ans2 == -1) {
    ans2 = U[ans];
  } else {
    ans2 = gg[ans2];
  }
  l = in[V[ans]], r = n; int ans3 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    for (auto i : spec) {
      x[i] = 0;
    }
    for (int j = in[V[ans]]; j <= mid; j++) {
      x[ind[gg[j]][p[gg[j]]]] = 1;
    }
    if (ask(x) != z) {
      r = mid - 1; ans3 = mid;
    } else {
      l = mid + 1;
    }
  }
  assert(ans3 != -1);
  ans3 = gg[ans3];
  answer(ans2, ans3);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 22872 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 4 ms 23128 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 25184 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 4 ms 23128 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 13 ms 24800 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 12 ms 24584 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -