oj.uz

Submission #222816

# Submission time Handle Problem Language Result Execution time Memory
222816 2020-04-14T03:57:18 Z rama_pang Highway Tolls (IOI18_highway) C++14
100 / 100
 222 ms 9292 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size(), E = -1;

  lint base_cost_light = ask(vector<int>(M, 0));
  lint base_cost_heavy = (base_cost_light / A) * B;
    
  vector<int> heavy;
  vector<int> edge_list[2]; // edges that are in the BFS tree of U[E] and V[E]

  { // Binary Search to find an edge E which is in the shortest path from S to T if unweighted 
    heavy.assign(M, 0);
    int lo = 0, hi = M - 1;
    
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      for (int i = 0; i < M; i++) heavy[i] = i <= mid;
      if (ask(heavy) != base_cost_light) { // one of the heavy edges we set is in the unweighted shortest path
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }

    E = hi;
  }

  { // Create BFS Tree from both ends of E
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
      adj[U[i]].emplace_back(i);
      adj[V[i]].emplace_back(i);
    }

    vector<bool> vis(N, false);
    queue<pair<int, int>> q;
    vis[U[E]] = vis[V[E]] = true;
    q.emplace(U[E], 0), q.emplace(V[E], 1);

    while (!q.empty()) {
      int u = q.front().first;
      int t = q.front().second;
      q.pop();
      for (auto e_id : adj[u]) {
        int to = (U[e_id] ^ V[e_id] ^ u);
        if  (vis[to]) continue;
        vis[to] = true;
        q.emplace(to, t);
        edge_list[t].emplace_back(e_id);
        if (V[e_id] == u) swap(U[e_id], V[e_id]); // U is nearer than V
      }
    }
  }
  
  auto Get = [&](int root, vector<int> edges) { // Binary Search to find S and T
    // set all edges not in the BFS Tree to heavy traffic
    heavy.assign(M, 1);
    heavy[E] = 0;
    for (int i = 0; i < 2; i++) {
      for (auto j : edge_list[i]) {
        heavy[j] = 0;
      }
    }

    int lo = -1, hi = edges.size() - 1;

    while (lo < hi) {
      int mid = (lo + hi + 1) >> 1;
      for (int i = 0; i < (int) edges.size(); i++) heavy[edges[i]] = i >= mid;
      if (ask(heavy) != base_cost_light) { // there is a heavy edge from S to T
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }

    return hi == -1 ? root : V[edges[hi]]; // heavy edge in the BFS Tree
  };

  return answer(Get(U[E], edge_list[0]), Get(V[E], edge_list[1]));  
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:10:8: warning: unused variable 'base_cost_heavy' [-Wunused-variable]
   lint base_cost_heavy = (base_cost_light / A) * B;
        ^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 17 ms 1152 KB Output is correct
3 Correct 147 ms 8044 KB Output is correct
4 Correct 143 ms 8108 KB Output is correct
5 Correct 143 ms 7948 KB Output is correct
6 Correct 121 ms 7948 KB Output is correct
7 Correct 147 ms 8136 KB Output is correct
8 Correct 143 ms 7948 KB Output is correct
9 Correct 131 ms 8000 KB Output is correct
10 Correct 139 ms 7944 KB Output is correct
11 Correct 147 ms 7688 KB Output is correct
12 Correct 150 ms 7948 KB Output is correct
13 Correct 154 ms 7948 KB Output is correct
14 Correct 168 ms 7944 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1280 KB Output is correct
2 Correct 31 ms 1912 KB Output is correct
3 Correct 42 ms 2752 KB Output is correct
4 Correct 130 ms 7556 KB Output is correct
5 Correct 118 ms 7588 KB Output is correct
6 Correct 121 ms 7892 KB Output is correct
7 Correct 121 ms 7908 KB Output is correct
8 Correct 123 ms 7632 KB Output is correct
9 Correct 127 ms 7904 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 18 ms 1180 KB Output is correct
3 Correct 117 ms 6368 KB Output is correct
4 Correct 141 ms 8076 KB Output is correct
5 Correct 137 ms 8020 KB Output is correct
6 Correct 136 ms 7948 KB Output is correct
7 Correct 136 ms 8076 KB Output is correct
8 Correct 135 ms 7948 KB Output is correct
9 Correct 152 ms 8024 KB Output is correct
10 Correct 144 ms 7948 KB Output is correct
11 Correct 158 ms 7948 KB Output is correct
12 Correct 145 ms 7904 KB Output is correct
13 Correct 181 ms 7944 KB Output is correct
14 Correct 164 ms 7564 KB Output is correct
15 Correct 153 ms 8056 KB Output is correct
16 Correct 134 ms 7956 KB Output is correct
17 Correct 150 ms 7948 KB Output is correct
18 Correct 153 ms 7880 KB Output is correct
19 Correct 135 ms 8020 KB Output is correct
20 Correct 143 ms 7924 KB Output is correct
21 Correct 120 ms 8604 KB Output is correct
22 Correct 112 ms 8528 KB Output is correct
23 Correct 135 ms 8204 KB Output is correct
24 Correct 131 ms 8204 KB Output is correct
25 Correct 143 ms 7948 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1152 KB Output is correct
2 Correct 20 ms 1272 KB Output is correct
3 Correct 164 ms 8160 KB Output is correct
4 Correct 188 ms 8572 KB Output is correct
5 Correct 219 ms 9292 KB Output is correct
6 Correct 218 ms 8800 KB Output is correct
7 Correct 217 ms 8984 KB Output is correct
8 Correct 221 ms 8924 KB Output is correct
9 Correct 161 ms 5504 KB Output is correct
10 Correct 164 ms 5808 KB Output is correct
11 Correct 174 ms 6524 KB Output is correct
12 Correct 199 ms 8032 KB Output is correct
13 Correct 205 ms 8544 KB Output is correct
14 Correct 209 ms 8776 KB Output is correct
15 Correct 207 ms 8804 KB Output is correct
16 Correct 188 ms 6756 KB Output is correct
17 Correct 134 ms 8588 KB Output is correct
18 Correct 128 ms 8724 KB Output is correct
19 Correct 132 ms 8576 KB Output is correct
20 Correct 138 ms 8812 KB Output is correct
21 Correct 201 ms 8924 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1152 KB Output is correct
2 Correct 20 ms 1280 KB Output is correct
3 Correct 174 ms 8284 KB Output is correct
4 Correct 175 ms 8392 KB Output is correct
5 Correct 182 ms 8248 KB Output is correct
6 Correct 221 ms 8872 KB Output is correct
7 Correct 170 ms 8248 KB Output is correct
8 Correct 173 ms 8368 KB Output is correct
9 Correct 189 ms 8364 KB Output is correct
10 Correct 202 ms 9140 KB Output is correct
11 Correct 212 ms 8924 KB Output is correct
12 Correct 208 ms 8888 KB Output is correct
13 Correct 166 ms 6400 KB Output is correct
14 Correct 173 ms 5768 KB Output is correct
15 Correct 191 ms 6316 KB Output is correct
16 Correct 169 ms 5820 KB Output is correct
17 Correct 166 ms 6620 KB Output is correct
18 Correct 173 ms 5804 KB Output is correct
19 Correct 183 ms 8052 KB Output is correct
20 Correct 200 ms 8544 KB Output is correct
21 Correct 218 ms 8796 KB Output is correct
22 Correct 209 ms 8808 KB Output is correct
23 Correct 213 ms 8788 KB Output is correct
24 Correct 213 ms 8916 KB Output is correct
25 Correct 210 ms 8872 KB Output is correct
26 Correct 207 ms 8928 KB Output is correct
27 Correct 129 ms 8796 KB Output is correct
28 Correct 133 ms 8572 KB Output is correct
29 Correct 129 ms 8696 KB Output is correct
30 Correct 136 ms 8576 KB Output is correct
31 Correct 136 ms 8688 KB Output is correct
32 Correct 139 ms 8588 KB Output is correct
33 Correct 139 ms 8840 KB Output is correct
34 Correct 133 ms 8652 KB Output is correct
35 Correct 131 ms 8648 KB Output is correct
36 Correct 142 ms 8580 KB Output is correct
37 Correct 137 ms 8780 KB Output is correct
38 Correct 135 ms 8560 KB Output is correct
39 Correct 197 ms 8928 KB Output is correct
40 Correct 204 ms 8928 KB Output is correct
41 Correct 206 ms 8928 KB Output is correct
42 Correct 222 ms 8664 KB Output is correct