oj.uz

Submission #1036471

# Submission time Handle Problem Language Result Execution time Memory
1036471 2024-07-27T12:07:59 Z abczz Highway Tolls (IOI18_highway) C++17
100 / 100
 166 ms 15076 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=0; i<N; ++i) visited[i] = 0;
    for (int i=mid; i>=0; --i) {
      visited[X[i]] = 1;
      if (!visited[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=0; i<N; ++i) visited[i] = 0;
    for (int i=mid; i>=0; --i) {
      visited[X[i]] = 1;
      if (!visited[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
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 10 ms 3652 KB Output is correct
3 Correct 92 ms 11792 KB Output is correct
4 Correct 93 ms 11904 KB Output is correct
5 Correct 89 ms 11736 KB Output is correct
6 Correct 93 ms 11712 KB Output is correct
7 Correct 86 ms 11880 KB Output is correct
8 Correct 110 ms 11704 KB Output is correct
9 Correct 84 ms 11884 KB Output is correct
10 Correct 107 ms 11720 KB Output is correct
11 Correct 89 ms 11960 KB Output is correct
12 Correct 88 ms 11900 KB Output is correct
13 Correct 86 ms 11984 KB Output is correct
14 Correct 94 ms 12008 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3416 KB Output is correct
2 Correct 17 ms 4332 KB Output is correct
3 Correct 25 ms 4676 KB Output is correct
4 Correct 65 ms 10412 KB Output is correct
5 Correct 62 ms 10432 KB Output is correct
6 Correct 76 ms 11160 KB Output is correct
7 Correct 64 ms 9168 KB Output is correct
8 Correct 79 ms 10380 KB Output is correct
9 Correct 70 ms 9848 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 9 ms 3648 KB Output is correct
3 Correct 84 ms 9400 KB Output is correct
4 Correct 89 ms 10956 KB Output is correct
5 Correct 94 ms 11820 KB Output is correct
6 Correct 79 ms 10600 KB Output is correct
7 Correct 85 ms 11232 KB Output is correct
8 Correct 97 ms 11536 KB Output is correct
9 Correct 110 ms 11880 KB Output is correct
10 Correct 94 ms 11712 KB Output is correct
11 Correct 94 ms 11176 KB Output is correct
12 Correct 93 ms 11772 KB Output is correct
13 Correct 97 ms 11780 KB Output is correct
14 Correct 87 ms 11652 KB Output is correct
15 Correct 102 ms 11380 KB Output is correct
16 Correct 80 ms 10968 KB Output is correct
17 Correct 94 ms 11552 KB Output is correct
18 Correct 87 ms 11132 KB Output is correct
19 Correct 74 ms 9932 KB Output is correct
20 Correct 77 ms 10964 KB Output is correct
21 Correct 93 ms 11604 KB Output is correct
22 Correct 91 ms 11016 KB Output is correct
23 Correct 89 ms 12232 KB Output is correct
24 Correct 79 ms 12120 KB Output is correct
25 Correct 96 ms 11800 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3672 KB Output is correct
2 Correct 11 ms 3720 KB Output is correct
3 Correct 115 ms 12712 KB Output is correct
4 Correct 108 ms 13300 KB Output is correct
5 Correct 166 ms 14732 KB Output is correct
6 Correct 147 ms 14632 KB Output is correct
7 Correct 143 ms 14880 KB Output is correct
8 Correct 140 ms 14928 KB Output is correct
9 Correct 108 ms 11212 KB Output is correct
10 Correct 107 ms 12256 KB Output is correct
11 Correct 99 ms 11824 KB Output is correct
12 Correct 137 ms 14040 KB Output is correct
13 Correct 155 ms 14868 KB Output is correct
14 Correct 143 ms 14880 KB Output is correct
15 Correct 141 ms 14796 KB Output is correct
16 Correct 116 ms 13664 KB Output is correct
17 Correct 92 ms 12228 KB Output is correct
18 Correct 92 ms 11864 KB Output is correct
19 Correct 89 ms 12304 KB Output is correct
20 Correct 89 ms 11416 KB Output is correct
21 Correct 133 ms 15036 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3896 KB Output is correct
2 Correct 11 ms 3664 KB Output is correct
3 Correct 104 ms 12480 KB Output is correct
4 Correct 111 ms 12940 KB Output is correct
5 Correct 122 ms 13196 KB Output is correct
6 Correct 120 ms 14956 KB Output is correct
7 Correct 101 ms 12540 KB Output is correct
8 Correct 101 ms 13052 KB Output is correct
9 Correct 122 ms 13588 KB Output is correct
10 Correct 134 ms 14964 KB Output is correct
11 Correct 153 ms 14656 KB Output is correct
12 Correct 144 ms 14980 KB Output is correct
13 Correct 113 ms 12096 KB Output is correct
14 Correct 134 ms 12932 KB Output is correct
15 Correct 109 ms 12576 KB Output is correct
16 Correct 127 ms 12720 KB Output is correct
17 Correct 113 ms 11896 KB Output is correct
18 Correct 106 ms 12876 KB Output is correct
19 Correct 117 ms 14196 KB Output is correct
20 Correct 136 ms 14656 KB Output is correct
21 Correct 148 ms 14772 KB Output is correct
22 Correct 153 ms 14792 KB Output is correct
23 Correct 158 ms 15008 KB Output is correct
24 Correct 144 ms 14832 KB Output is correct
25 Correct 144 ms 13924 KB Output is correct
26 Correct 137 ms 14912 KB Output is correct
27 Correct 93 ms 11768 KB Output is correct
28 Correct 112 ms 11440 KB Output is correct
29 Correct 94 ms 11728 KB Output is correct
30 Correct 92 ms 11040 KB Output is correct
31 Correct 93 ms 11656 KB Output is correct
32 Correct 94 ms 11264 KB Output is correct
33 Correct 91 ms 12032 KB Output is correct
34 Correct 91 ms 12220 KB Output is correct
35 Correct 91 ms 12288 KB Output is correct
36 Correct 86 ms 11472 KB Output is correct
37 Correct 110 ms 11776 KB Output is correct
38 Correct 113 ms 11152 KB Output is correct
39 Correct 134 ms 14896 KB Output is correct
40 Correct 135 ms 15052 KB Output is correct
41 Correct 141 ms 14884 KB Output is correct
42 Correct 131 ms 15076 KB Output is correct