oj.uz

Submission #836202

# Submission time Handle Problem Language Result Execution time Memory
836202 2023-08-24T08:41:35 Z Johann Highway Tolls (IOI18_highway) C++14
51 / 100
 193 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; base + (i << j) < sz(cand); 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 << j) + base < M; 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 7 ms 1244 KB Output is correct
3 Correct 73 ms 9168 KB Output is correct
4 Correct 75 ms 9076 KB Output is correct
5 Correct 103 ms 9160 KB Output is correct
6 Correct 76 ms 9024 KB Output is correct
7 Correct 96 ms 9080 KB Output is correct
8 Correct 72 ms 9184 KB Output is correct
9 Correct 67 ms 8932 KB Output is correct
10 Correct 110 ms 9176 KB Output is correct
11 Correct 115 ms 9308 KB Output is correct
12 Correct 77 ms 9784 KB Output is correct
13 Correct 70 ms 9408 KB Output is correct
14 Correct 90 ms 9320 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1560 KB Output is correct
2 Correct 34 ms 2844 KB Output is correct
3 Correct 19 ms 4232 KB Output is correct
4 Correct 55 ms 10748 KB Output is correct
5 Correct 73 ms 10984 KB Output is correct
6 Correct 51 ms 11380 KB Output is correct
7 Correct 63 ms 12364 KB Output is correct
8 Correct 114 ms 11024 KB Output is correct
9 Correct 57 ms 11564 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 11 ms 1264 KB Output is correct
3 Correct 79 ms 6988 KB Output is correct
4 Correct 60 ms 9020 KB Output is correct
5 Correct 103 ms 8940 KB Output is correct
6 Correct 76 ms 8960 KB Output is correct
7 Correct 109 ms 8952 KB Output is correct
8 Correct 76 ms 8864 KB Output is correct
9 Correct 68 ms 8936 KB Output is correct
10 Correct 87 ms 9184 KB Output is correct
11 Correct 108 ms 9252 KB Output is correct
12 Correct 91 ms 9928 KB Output is correct
13 Correct 75 ms 9272 KB Output is correct
14 Correct 92 ms 9608 KB Output is correct
15 Correct 70 ms 9064 KB Output is correct
16 Correct 86 ms 8940 KB Output is correct
17 Correct 69 ms 9180 KB Output is correct
18 Correct 68 ms 9676 KB Output is correct
19 Correct 72 ms 8956 KB Output is correct
20 Correct 75 ms 9932 KB Output is correct
21 Correct 77 ms 10572 KB Output is correct
22 Correct 64 ms 10688 KB Output is correct
23 Correct 70 ms 10064 KB Output is correct
24 Correct 107 ms 10184 KB Output is correct
25 Correct 95 ms 11228 KB Output is correct

Subtask #5
0 / 18.0

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