| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 292271 | 2020-09-06T17:03:31 Z | SamAnd | Highway Tolls (IOI18_highway) | C++17 | 299 ms | 262148 KB |
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
int n, m;
vector<int> g[N];
vector<int> gi[N];
int d[N];
int u[N];
void dfs0(int x, int p)
{
if (x == p)
d[x] = 0;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (h == p)
{
u[x] = gi[x][i];
continue;
}
d[h] = d[x] + 1;
dfs0(h, x);
}
}
void find_pair(int N_, std::vector<int> U, std::vector<int> V, int A, int B)
{
n = N_;
m = sz(U);
for (int i = 0; i < m; ++i)
{
int x = U[i];
int y = V[i];
g[x].push_back(y);
g[y].push_back(x);
gi[x].push_back(i);
gi[y].push_back(i);
}
vector<int> v;
v.assign(m, 0);
int dd = ask(v) / A;
dfs0(0, 0);
int maxu = 0;
for (int x = 0; x < n; ++x)
maxu = max(maxu, d[x]);
int l = 1, r = maxu;
int ans;
while (l <= r)
{
int mid = (l + r) / 2;
v.assign(m, 0);
for (int x = 0; x < n; ++x)
{
if (d[x] >= mid)
{
v[u[x]] = 1;
}
}
if (ask(v) != dd * 1LL * A)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
vector<int> t;
for (int x = 0; x < n; ++x)
{
if (d[x] == ans)
{
t.push_back(x);
}
}
int ans1;
{
int l = 0, r = sz(t) - 1;
int ans;
while (l <= r)
{
int mid = (l + r) / 2;
v.assign(m, 0);
for (int i = 0; i <= mid; ++i)
{
v[u[t[i]]] = 1;
}
if (ask(v) != dd * 1LL * A)
{
ans = t[mid];
r = mid - 1;
}
else
l = mid + 1;
}
ans1 = ans;
}
dfs0(ans1, ans1);
t.clear();
for (int x = 0; x < n; ++x)
{
if (d[x] == dd)
{
t.push_back(x);
}
}
int ans2;
{
int l = 0, r = sz(t) - 1;
int ans;
while (l <= r)
{
int mid = (l + r) / 2;
v.assign(m, 0);
for (int i = 0; i <= mid; ++i)
{
v[u[t[i]]] = 1;
}
if (ask(v) != dd * 1LL * A)
{
ans = t[mid];
r = mid - 1;
}
else
l = mid + 1;
}
ans2 = ans;
}
answer(ans1, ans2);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 4992 KB | Output is correct |
| 2 | Correct | 4 ms | 4992 KB | Output is correct |
| 3 | Correct | 4 ms | 4992 KB | Output is correct |
| 4 | Correct | 4 ms | 4992 KB | Output is correct |
| 5 | Correct | 4 ms | 4992 KB | Output is correct |
| 6 | Correct | 4 ms | 5084 KB | Output is correct |
| 7 | Correct | 4 ms | 4992 KB | Output is correct |
| 8 | Correct | 3 ms | 5084 KB | Output is correct |
| 9 | Correct | 4 ms | 4992 KB | Output is correct |
| 10 | Correct | 5 ms | 5024 KB | Output is correct |
| 11 | Correct | 4 ms | 4992 KB | Output is correct |
| 12 | Correct | 4 ms | 5080 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 5160 KB | Output is correct |
| 2 | Correct | 18 ms | 5888 KB | Output is correct |
| 3 | Correct | 206 ms | 13616 KB | Output is correct |
| 4 | Correct | 181 ms | 13488 KB | Output is correct |
| 5 | Correct | 185 ms | 13584 KB | Output is correct |
| 6 | Correct | 190 ms | 13524 KB | Output is correct |
| 7 | Correct | 195 ms | 13572 KB | Output is correct |
| 8 | Correct | 193 ms | 13512 KB | Output is correct |
| 9 | Correct | 192 ms | 13544 KB | Output is correct |
| 10 | Correct | 195 ms | 13492 KB | Output is correct |
| 11 | Correct | 211 ms | 14620 KB | Output is correct |
| 12 | Correct | 207 ms | 15296 KB | Output is correct |
| 13 | Correct | 211 ms | 14740 KB | Output is correct |
| 14 | Correct | 200 ms | 14708 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 6656 KB | Output is correct |
| 2 | Correct | 32 ms | 8088 KB | Output is correct |
| 3 | Correct | 42 ms | 9592 KB | Output is correct |
| 4 | Correct | 130 ms | 18820 KB | Output is correct |
| 5 | Correct | 157 ms | 18928 KB | Output is correct |
| 6 | Correct | 132 ms | 18808 KB | Output is correct |
| 7 | Correct | 126 ms | 18808 KB | Output is correct |
| 8 | Correct | 124 ms | 18844 KB | Output is correct |
| 9 | Correct | 170 ms | 18812 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 5120 KB | Output is correct |
| 2 | Correct | 20 ms | 6016 KB | Output is correct |
| 3 | Correct | 138 ms | 11604 KB | Output is correct |
| 4 | Correct | 193 ms | 13496 KB | Output is correct |
| 5 | Correct | 236 ms | 13448 KB | Output is correct |
| 6 | Correct | 196 ms | 13600 KB | Output is correct |
| 7 | Correct | 235 ms | 13448 KB | Output is correct |
| 8 | Correct | 198 ms | 13544 KB | Output is correct |
| 9 | Correct | 218 ms | 13608 KB | Output is correct |
| 10 | Correct | 252 ms | 13512 KB | Output is correct |
| 11 | Correct | 241 ms | 14380 KB | Output is correct |
| 12 | Correct | 208 ms | 15244 KB | Output is correct |
| 13 | Correct | 190 ms | 14872 KB | Output is correct |
| 14 | Correct | 215 ms | 15284 KB | Output is correct |
| 15 | Correct | 182 ms | 13460 KB | Output is correct |
| 16 | Correct | 188 ms | 13440 KB | Output is correct |
| 17 | Correct | 244 ms | 14916 KB | Output is correct |
| 18 | Correct | 259 ms | 14968 KB | Output is correct |
| 19 | Correct | 230 ms | 13456 KB | Output is correct |
| 20 | Correct | 212 ms | 15756 KB | Output is correct |
| 21 | Correct | 215 ms | 14656 KB | Output is correct |
| 22 | Correct | 192 ms | 14656 KB | Output is correct |
| 23 | Correct | 232 ms | 14324 KB | Output is correct |
| 24 | Correct | 197 ms | 14940 KB | Output is correct |
| 25 | Correct | 268 ms | 18328 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 299 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 | 276 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |