| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 116496 | 2019-06-12T15:49:24 Z | mirbek01 | Highway Tolls (IOI18_highway) | C++11 | 512 ms | 262148 KB |
# include <bits/stdc++.h>
# include "highway.h"
using namespace std;
const int maxn = 2e5 + 2;
int d[maxn], pr[maxn], used[maxn];
long long len, lenB;
vector < pair <int, int> > g[maxn];
vector <int> vec, Ua, Va;
void dfs(int v, int par){
vec.push_back(v);
for(int i = 0; i < g[v].size(); i ++){
int to = g[v][i].first;
if(to == par)
continue;
d[to] = d[v] + 1;
pr[to] = g[v][i].second;
used[g[v][i].second] = 1;
dfs(to, v);
}
}
bool cmp(int a, int b){
return d[a] < d[b];
}
int f(int ver, int e){
vec.clear();
memset(used, 0, sizeof(used));
if(ver == Ua[e])
dfs(ver, Va[e]);
else
dfs(ver, Ua[e]);
pr[ver] = e;
used[e] = 1;
int ans, l = 0, r = (int)vec.size() - 1;
sort(vec.begin(), vec.end(), cmp);
while(l <= r){
int md = (l + r) >> 1;
vector <int> w(Ua.size(), 0);
for(int i = 0; i <= md; i ++){
w[pr[vec[i]]] = 1;
}
for(int i = 0; i < Ua.size(); i ++){
if(!used[i])
w[i] = 1;
}
long long ret = ask(w);
if(ret == lenB)
r = md - 1, ans = vec[md];
else
l = md + 1;
}
return ans;
}
void find_pair(int N, vector<int> AB, vector<int> BA, int A, int B) {
Ua = AB;
Va = BA;
for(int i = 0; i < Ua.size(); i ++){
g[Ua[i]].push_back({Va[i], i});
g[Va[i]].push_back({Ua[i], i});
}
vector <int> w(Ua.size(), 0);
len = ask(w);
for(int i = 0; i < w.size(); i ++)
w[i] = 1;
lenB = ask(w);
int l = 0, r = (int)Ua.size() - 1, e;
while(l <= r){
int md = (l + r) >> 1;
for(int i = 0; i < w.size(); i ++)
w[i] = 0;
for(int i = 0; i <= md; i ++)
w[i] = 1;
long long ret = ask(w);
if(len == ret)
l = md + 1;
else
r = md - 1, e = md;
}
answer(f(Ua[e], e), f(Va[e], e));
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 5800 KB | Output is correct |
| 2 | Correct | 7 ms | 5752 KB | Output is correct |
| 3 | Correct | 7 ms | 5884 KB | Output is correct |
| 4 | Correct | 7 ms | 5796 KB | Output is correct |
| 5 | Correct | 7 ms | 5800 KB | Output is correct |
| 6 | Correct | 7 ms | 5756 KB | Output is correct |
| 7 | Correct | 7 ms | 5800 KB | Output is correct |
| 8 | Correct | 7 ms | 5820 KB | Output is correct |
| 9 | Correct | 7 ms | 5796 KB | Output is correct |
| 10 | Correct | 6 ms | 5800 KB | Output is correct |
| 11 | Correct | 7 ms | 5804 KB | Output is correct |
| 12 | Correct | 7 ms | 5752 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 5880 KB | Output is correct |
| 2 | Correct | 28 ms | 6576 KB | Output is correct |
| 3 | Correct | 240 ms | 13244 KB | Output is correct |
| 4 | Correct | 244 ms | 13136 KB | Output is correct |
| 5 | Correct | 215 ms | 13168 KB | Output is correct |
| 6 | Correct | 258 ms | 13176 KB | Output is correct |
| 7 | Correct | 243 ms | 13188 KB | Output is correct |
| 8 | Correct | 218 ms | 13108 KB | Output is correct |
| 9 | Correct | 193 ms | 13336 KB | Output is correct |
| 10 | Correct | 199 ms | 13172 KB | Output is correct |
| 11 | Correct | 259 ms | 13212 KB | Output is correct |
| 12 | Correct | 282 ms | 13828 KB | Output is correct |
| 13 | Correct | 260 ms | 13640 KB | Output is correct |
| 14 | Correct | 248 ms | 13752 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 6892 KB | Output is correct |
| 2 | Correct | 48 ms | 8116 KB | Output is correct |
| 3 | Correct | 63 ms | 9188 KB | Output is correct |
| 4 | Correct | 183 ms | 15028 KB | Output is correct |
| 5 | Correct | 191 ms | 15036 KB | Output is correct |
| 6 | Correct | 205 ms | 15832 KB | Output is correct |
| 7 | Correct | 159 ms | 16672 KB | Output is correct |
| 8 | Correct | 187 ms | 15392 KB | Output is correct |
| 9 | Correct | 175 ms | 15568 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 5984 KB | Output is correct |
| 2 | Correct | 31 ms | 6572 KB | Output is correct |
| 3 | Correct | 185 ms | 11516 KB | Output is correct |
| 4 | Correct | 184 ms | 13196 KB | Output is correct |
| 5 | Correct | 180 ms | 13264 KB | Output is correct |
| 6 | Correct | 184 ms | 13148 KB | Output is correct |
| 7 | Correct | 183 ms | 13224 KB | Output is correct |
| 8 | Correct | 218 ms | 13232 KB | Output is correct |
| 9 | Correct | 216 ms | 13208 KB | Output is correct |
| 10 | Correct | 205 ms | 13232 KB | Output is correct |
| 11 | Correct | 242 ms | 13552 KB | Output is correct |
| 12 | Correct | 287 ms | 13884 KB | Output is correct |
| 13 | Correct | 255 ms | 13644 KB | Output is correct |
| 14 | Correct | 264 ms | 13548 KB | Output is correct |
| 15 | Correct | 178 ms | 13184 KB | Output is correct |
| 16 | Correct | 212 ms | 13304 KB | Output is correct |
| 17 | Correct | 242 ms | 13716 KB | Output is correct |
| 18 | Correct | 249 ms | 13908 KB | Output is correct |
| 19 | Correct | 191 ms | 13236 KB | Output is correct |
| 20 | Correct | 215 ms | 14136 KB | Output is correct |
| 21 | Correct | 179 ms | 13400 KB | Output is correct |
| 22 | Correct | 160 ms | 13404 KB | Output is correct |
| 23 | Correct | 206 ms | 13376 KB | Output is correct |
| 24 | Correct | 246 ms | 13556 KB | Output is correct |
| 25 | Correct | 256 ms | 16332 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 512 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 466 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |