| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 361705 | 2021-01-31T09:58:56 Z | cuongdh1912 | Highway Tolls (IOI18_highway) | C++14 | 214 ms | 9552 KB |
#include "highway.h"
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<vector>
#include<cstdint>
#include<algorithm>
#include <array>
#include <queue>
using namespace std;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = (int)U.size();
vector<int> w;
w.resize(M, 0);
const auto d = ask(w);
int i = 0;
// find the maximum of index where there is no shortest path has edge in 0..<i
// therefore there must be an edge index i the shortest path have
for (auto step = 1<<20; step>>=1;) {
if (i + step < M) {
w.assign(i+step, 1);
w.resize(M, 0);
if (d == ask(w)) {
i += step;
}
}
}
struct Edge { int node, index;};
vector<vector<Edge> > add(N);
for (int j = 0; j < M; ++j) {
int a = U[j]; int b = V[j];
add[a].push_back({b, j});
add[b].push_back({a, j});
}
array<vector<Edge>, 2> edges;
edges[0].push_back({U[i], i});
edges[1].push_back({V[i], i});
vector<bool> visited(M, false);
visited[edges[0][0].node] = true;
visited[edges[1][0].node] = true;
for (int j = 0; j < edges.size(); ++j) {
// find maximum
queue<int> q;
q.push(edges[j][0].node);
while (q.size() > 0) {
int v = q.front(); q.pop();
for (auto e: add[v]) {
if (!visited[e.node]) {
visited[e.node] = true;
q.push(e.node);
edges[j].push_back(e);
}
}
}
}
int ans[2];
for (int j = 0; j < edges.size(); ++j ) {
int k = (int)edges[j].size();
for (int step = 1<<20; step>>=1; ) {
if (k - step > 0) {
w.assign(M, 1);
w[i] = 0;
for (int l = 0; l < k - step; ++l) w[edges[j][l].index] = 0;
for (int l = 0; l < edges[!j].size(); ++l ) w[edges[!j][l].index] = 0;
if (d == ask(w)) {
k -= step;
}
}
}
ans[j] = edges[j][k-1].node;
}
answer(ans[0], ans[1]);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| 3 | Correct | 1 ms | 364 KB | Output is correct |
| 4 | Correct | 0 ms | 364 KB | Output is correct |
| 5 | Correct | 1 ms | 364 KB | Output is correct |
| 6 | Correct | 1 ms | 364 KB | Output is correct |
| 7 | Correct | 1 ms | 364 KB | Output is correct |
| 8 | Correct | 1 ms | 364 KB | Output is correct |
| 9 | Correct | 1 ms | 364 KB | Output is correct |
| 10 | Correct | 1 ms | 364 KB | Output is correct |
| 11 | Correct | 1 ms | 364 KB | Output is correct |
| 12 | Correct | 1 ms | 364 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 15 ms | 1280 KB | Output is correct |
| 3 | Correct | 147 ms | 8804 KB | Output is correct |
| 4 | Correct | 149 ms | 8816 KB | Output is correct |
| 5 | Correct | 154 ms | 8740 KB | Output is correct |
| 6 | Correct | 184 ms | 8880 KB | Output is correct |
| 7 | Correct | 152 ms | 8808 KB | Output is correct |
| 8 | Correct | 137 ms | 8808 KB | Output is correct |
| 9 | Correct | 139 ms | 8732 KB | Output is correct |
| 10 | Correct | 172 ms | 8808 KB | Output is correct |
| 11 | Correct | 149 ms | 8268 KB | Output is correct |
| 12 | Correct | 146 ms | 8144 KB | Output is correct |
| 13 | Correct | 142 ms | 8300 KB | Output is correct |
| 14 | Correct | 154 ms | 8140 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 1260 KB | Output is correct |
| 2 | Correct | 26 ms | 2148 KB | Output is correct |
| 3 | Correct | 40 ms | 2868 KB | Output is correct |
| 4 | Correct | 137 ms | 8200 KB | Output is correct |
| 5 | Correct | 115 ms | 8084 KB | Output is correct |
| 6 | Correct | 124 ms | 8340 KB | Output is correct |
| 7 | Correct | 157 ms | 8124 KB | Output is correct |
| 8 | Correct | 162 ms | 7908 KB | Output is correct |
| 9 | Correct | 152 ms | 8416 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 16 ms | 1260 KB | Output is correct |
| 3 | Correct | 109 ms | 7148 KB | Output is correct |
| 4 | Correct | 178 ms | 8868 KB | Output is correct |
| 5 | Correct | 135 ms | 8744 KB | Output is correct |
| 6 | Correct | 113 ms | 8800 KB | Output is correct |
| 7 | Correct | 131 ms | 8804 KB | Output is correct |
| 8 | Correct | 127 ms | 8804 KB | Output is correct |
| 9 | Correct | 174 ms | 8736 KB | Output is correct |
| 10 | Correct | 171 ms | 8816 KB | Output is correct |
| 11 | Correct | 190 ms | 8136 KB | Output is correct |
| 12 | Correct | 148 ms | 8396 KB | Output is correct |
| 13 | Correct | 202 ms | 8264 KB | Output is correct |
| 14 | Correct | 179 ms | 8084 KB | Output is correct |
| 15 | Correct | 169 ms | 8804 KB | Output is correct |
| 16 | Correct | 129 ms | 8752 KB | Output is correct |
| 17 | Correct | 165 ms | 8136 KB | Output is correct |
| 18 | Correct | 194 ms | 8136 KB | Output is correct |
| 19 | Correct | 135 ms | 8748 KB | Output is correct |
| 20 | Correct | 145 ms | 8388 KB | Output is correct |
| 21 | Correct | 123 ms | 9552 KB | Output is correct |
| 22 | Correct | 156 ms | 9436 KB | Output is correct |
| 23 | Correct | 214 ms | 8884 KB | Output is correct |
| 24 | Correct | 139 ms | 8760 KB | Output is correct |
| 25 | Correct | 171 ms | 8392 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 16 ms | 1388 KB | Output is incorrect: {s, t} is wrong. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 15 ms | 1388 KB | Output is incorrect: {s, t} is wrong. |
| 2 | Halted | 0 ms | 0 KB | - |