oj.uz

Submission #836187

# Submission time Handle Problem Language Result Execution time Memory
836187 2023-08-24T08:29:45 Z Johann Highway Tolls (IOI18_highway) C++14
0 / 100
 189 ms 262144 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M;
vvpii adj;
vi par, depth;
std::vector<int> W;
ll shortest;
ll A, B;

void dfs(int v, int p)
{
  depth[v] = depth[p] + 1;
  for (pii e : adj[v])
    if (e.first != p)
      par[e.first] = e.second, dfs(e.first, v);
}

int findStuff(int v, int u, int eidx)
{
  par.assign(N, -1);
  depth.assign(N, 0);
  par[v] = eidx;
  dfs(v, u);
  W.assign(M, 0);
  for (int i = 0; i < N; ++i)
    if (par[i] != -1)
      W[par[i]] = 1;
  int d = (ask(W) - shortest) / (B - A);
  assert(d > 0);
  vi cand;
  for (int i = 0; i < N; ++i)
    if (depth[i] == d)
      cand.push_back(i);

  int base = 0;
  for (int j = 0; (1 << j) < sz(cand); ++j)
  {
    W.assign(M, 0);
    for (int i = 1; i < (sz(cand) >> j); i += 2)
      W[par[cand[base + (i << j)]]] = 1;

    if (shortest < ask(W))
      base |= 1 << j;
  }
  return cand[base];
}

void find_pair(int _N, std::vector<int> U, std::vector<int> V, int _A, int _B)
{
  N = _N, M = U.size();
  A = _A, B = _B;
  adj = vvpii(N);
  for (int i = 0; i < M; ++i)
    adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});

  W.assign(M, 0);
  shortest = ask(W);

  // find edge on shortest path
  int base = 0;
  for (int j = 0; (1 << j) < M; ++j)
  {
    W.assign(M, 0);
    for (int i = 1; i < (M >> j); i += 2)
      W[base + (i << j)] = 1;

    if (shortest < ask(W))
      base |= 1 << j;
  }

  // find distance of s and t to this edge
  int s = findStuff(U[base], V[base], base);
  int t = findStuff(V[base], U[base], base);

  answer(s, t);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 208 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 7 ms 2384 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1488 KB Output is correct
2 Correct 12 ms 2816 KB Output is correct
3 Runtime error 25 ms 6008 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 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 150 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -