| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 250309 | 2020-07-17T11:25:12 Z | Osama_Alkhodairy | Highway Tolls (IOI18_highway) | C++17 | 416 ms | 12556 KB |
#include <bits/stdc++.h>
#include "highway.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
int n, m;
vector <pair <int, int> > es, g[90001];
ll light;
int dist;
int find(int root){
vector <bool> vis(n);
queue <int> ready;
vector <int> depth(n);
ready.push(root);
vector <int> nodes;
vis[root] = 1;
while(ready.size()){
int node = ready.front();
ready.pop();
nodes.push_back(node);
for(auto &i : g[node]){
if(vis[i.first]) continue;
vis[i.first] = 1;
depth[i.first] = depth[node] + 1;
ready.push(i.first);
}
}
reverse(nodes.begin(), nodes.end());
vis.assign(m, 0);
vector <int> edges;
for(auto &i : nodes){
for(auto &j : g[i]){
if(vis[j.second]) continue;
vis[j.second] = 1;
edges.push_back(j.second);
}
}
int l = 0, r = m - 1;
while(l <= r){
int mid = (l + r) / 2;
vector <int> check(m);
for(int i = 0 ; i <= mid ; i++){
check[edges[i]] = 1;
}
if(ask(check) != light) r = mid - 1;
else l = mid + 1;
}
auto edge = es[edges[l]];
if(depth[edge.first] > depth[edge.second]) return edge.first;
return edge.second;
}
void find_pair(int N, std::vector<int> u, std::vector<int> v, int a, int b) {
n = N;
m = u.size();
for(int i = 0 ; i < m ; i++){
g[u[i]].push_back(make_pair(v[i], i));
g[v[i]].push_back(make_pair(u[i], i));
es.push_back(make_pair(u[i], v[i]));
}
light = ask(vector <int>(m, 0));
dist = light / a;
int l = 0, r = m - 1;
while(l <= r){
int mid = (l + r) / 2;
vector <int> check(m);
for(int i = 0 ; i <= mid ; i++){
check[i] = 1;
}
if(ask(check) != light) r = mid - 1;
else l = mid + 1;
}
int root = es[l].first;
int s = find(root);
int t = find(s);
answer(s, t);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 2432 KB | Output is correct |
| 2 | Correct | 2 ms | 2432 KB | Output is correct |
| 3 | Correct | 2 ms | 2432 KB | Output is correct |
| 4 | Correct | 2 ms | 2432 KB | Output is correct |
| 5 | Correct | 2 ms | 2432 KB | Output is correct |
| 6 | Correct | 2 ms | 2432 KB | Output is correct |
| 7 | Correct | 2 ms | 2432 KB | Output is correct |
| 8 | Correct | 2 ms | 2432 KB | Output is correct |
| 9 | Correct | 2 ms | 2432 KB | Output is correct |
| 10 | Correct | 2 ms | 2432 KB | Output is correct |
| 11 | Correct | 2 ms | 2432 KB | Output is correct |
| 12 | Correct | 2 ms | 2432 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 2560 KB | Output is correct |
| 2 | Correct | 15 ms | 3260 KB | Output is correct |
| 3 | Correct | 188 ms | 10036 KB | Output is correct |
| 4 | Correct | 303 ms | 10028 KB | Output is correct |
| 5 | Correct | 278 ms | 10088 KB | Output is correct |
| 6 | Correct | 268 ms | 10080 KB | Output is correct |
| 7 | Correct | 287 ms | 10212 KB | Output is correct |
| 8 | Correct | 212 ms | 10020 KB | Output is correct |
| 9 | Correct | 170 ms | 10116 KB | Output is correct |
| 10 | Correct | 167 ms | 10008 KB | Output is correct |
| 11 | Correct | 261 ms | 9732 KB | Output is correct |
| 12 | Correct | 289 ms | 9940 KB | Output is correct |
| 13 | Correct | 303 ms | 9728 KB | Output is correct |
| 14 | Correct | 284 ms | 9744 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 3236 KB | Output is correct |
| 2 | Correct | 48 ms | 4084 KB | Output is correct |
| 3 | Correct | 73 ms | 4864 KB | Output is correct |
| 4 | Correct | 114 ms | 9796 KB | Output is correct |
| 5 | Correct | 231 ms | 9864 KB | Output is correct |
| 6 | Correct | 215 ms | 9712 KB | Output is correct |
| 7 | Correct | 242 ms | 9780 KB | Output is correct |
| 8 | Correct | 122 ms | 9708 KB | Output is correct |
| 9 | Correct | 143 ms | 9776 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 2560 KB | Output is correct |
| 2 | Correct | 16 ms | 3268 KB | Output is correct |
| 3 | Correct | 189 ms | 8800 KB | Output is correct |
| 4 | Correct | 269 ms | 10024 KB | Output is correct |
| 5 | Correct | 151 ms | 10012 KB | Output is correct |
| 6 | Correct | 269 ms | 10024 KB | Output is correct |
| 7 | Correct | 159 ms | 10128 KB | Output is correct |
| 8 | Correct | 188 ms | 10012 KB | Output is correct |
| 9 | Correct | 260 ms | 10012 KB | Output is correct |
| 10 | Correct | 175 ms | 10056 KB | Output is correct |
| 11 | Correct | 167 ms | 9724 KB | Output is correct |
| 12 | Correct | 158 ms | 9724 KB | Output is correct |
| 13 | Correct | 166 ms | 9776 KB | Output is correct |
| 14 | Correct | 162 ms | 9724 KB | Output is correct |
| 15 | Correct | 159 ms | 10036 KB | Output is correct |
| 16 | Correct | 162 ms | 10032 KB | Output is correct |
| 17 | Correct | 160 ms | 9736 KB | Output is correct |
| 18 | Correct | 281 ms | 9736 KB | Output is correct |
| 19 | Correct | 213 ms | 10172 KB | Output is correct |
| 20 | Correct | 310 ms | 9724 KB | Output is correct |
| 21 | Correct | 238 ms | 10188 KB | Output is correct |
| 22 | Correct | 118 ms | 10112 KB | Output is correct |
| 23 | Correct | 228 ms | 10308 KB | Output is correct |
| 24 | Correct | 194 ms | 9928 KB | Output is correct |
| 25 | Correct | 164 ms | 9548 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 3320 KB | Output is correct |
| 2 | Correct | 29 ms | 3368 KB | Output is correct |
| 3 | Correct | 258 ms | 10380 KB | Output is correct |
| 4 | Correct | 287 ms | 10924 KB | Output is correct |
| 5 | Correct | 276 ms | 12256 KB | Output is correct |
| 6 | Correct | 397 ms | 12296 KB | Output is correct |
| 7 | Correct | 225 ms | 12300 KB | Output is correct |
| 8 | Correct | 218 ms | 12416 KB | Output is correct |
| 9 | Correct | 173 ms | 10340 KB | Output is correct |
| 10 | Correct | 305 ms | 10968 KB | Output is correct |
| 11 | Correct | 322 ms | 11328 KB | Output is correct |
| 12 | Correct | 379 ms | 12036 KB | Output is correct |
| 13 | Correct | 252 ms | 12244 KB | Output is correct |
| 14 | Correct | 228 ms | 12408 KB | Output is correct |
| 15 | Correct | 226 ms | 12556 KB | Output is correct |
| 16 | Correct | 182 ms | 11360 KB | Output is correct |
| 17 | Correct | 132 ms | 10132 KB | Output is correct |
| 18 | Correct | 145 ms | 10400 KB | Output is correct |
| 19 | Correct | 136 ms | 10248 KB | Output is correct |
| 20 | Correct | 157 ms | 10472 KB | Output is correct |
| 21 | Correct | 229 ms | 12224 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 32 ms | 3372 KB | Output is correct |
| 2 | Correct | 17 ms | 3368 KB | Output is correct |
| 3 | Partially correct | 177 ms | 10332 KB | Output is partially correct |
| 4 | Correct | 335 ms | 10664 KB | Output is correct |
| 5 | Partially correct | 312 ms | 10920 KB | Output is partially correct |
| 6 | Partially correct | 346 ms | 12332 KB | Output is partially correct |
| 7 | Partially correct | 172 ms | 10488 KB | Output is partially correct |
| 8 | Partially correct | 180 ms | 10604 KB | Output is partially correct |
| 9 | Partially correct | 190 ms | 10596 KB | Output is partially correct |
| 10 | Partially correct | 416 ms | 12360 KB | Output is partially correct |
| 11 | Partially correct | 259 ms | 12288 KB | Output is partially correct |
| 12 | Partially correct | 242 ms | 12304 KB | Output is partially correct |
| 13 | Partially correct | 350 ms | 11280 KB | Output is partially correct |
| 14 | Partially correct | 186 ms | 11168 KB | Output is partially correct |
| 15 | Partially correct | 178 ms | 11416 KB | Output is partially correct |
| 16 | Partially correct | 178 ms | 11108 KB | Output is partially correct |
| 17 | Partially correct | 278 ms | 11316 KB | Output is partially correct |
| 18 | Partially correct | 261 ms | 11084 KB | Output is partially correct |
| 19 | Partially correct | 395 ms | 11876 KB | Output is partially correct |
| 20 | Partially correct | 220 ms | 12100 KB | Output is partially correct |
| 21 | Partially correct | 369 ms | 12484 KB | Output is partially correct |
| 22 | Partially correct | 346 ms | 12556 KB | Output is partially correct |
| 23 | Partially correct | 252 ms | 12392 KB | Output is partially correct |
| 24 | Partially correct | 240 ms | 12408 KB | Output is partially correct |
| 25 | Partially correct | 221 ms | 12412 KB | Output is partially correct |
| 26 | Partially correct | 327 ms | 12532 KB | Output is partially correct |
| 27 | Partially correct | 170 ms | 10268 KB | Output is partially correct |
| 28 | Partially correct | 154 ms | 10348 KB | Output is partially correct |
| 29 | Partially correct | 138 ms | 10672 KB | Output is partially correct |
| 30 | Partially correct | 153 ms | 10392 KB | Output is partially correct |
| 31 | Correct | 143 ms | 10308 KB | Output is correct |
| 32 | Partially correct | 149 ms | 10148 KB | Output is partially correct |
| 33 | Partially correct | 143 ms | 10416 KB | Output is partially correct |
| 34 | Correct | 170 ms | 10292 KB | Output is correct |
| 35 | Partially correct | 136 ms | 10216 KB | Output is partially correct |
| 36 | Partially correct | 134 ms | 10116 KB | Output is partially correct |
| 37 | Partially correct | 151 ms | 10532 KB | Output is partially correct |
| 38 | Correct | 274 ms | 10264 KB | Output is correct |
| 39 | Partially correct | 370 ms | 12392 KB | Output is partially correct |
| 40 | Partially correct | 268 ms | 12292 KB | Output is partially correct |
| 41 | Partially correct | 381 ms | 12348 KB | Output is partially correct |
| 42 | Partially correct | 291 ms | 12296 KB | Output is partially correct |