| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114448 |
2019-06-01T11:22:53 Z |
mosesmayer |
Race (IOI11_race) |
C++17 |
|
97 ms |
18772 KB |
#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int MXN = 1e6;
const int mxsz = 2e5 + 3;
int n, k;
vector<pii> adj[mxsz];
int sz[mxsz], dep[mxsz], bc[mxsz], in[mxsz], out[mxsz], flat[mxsz];
long long dist[mxsz];
int sack[MXN + 10];
void getsz(int u, int prv = -1){
static int tme = 0;
in[u] = ++tme; flat[tme] = u;
sz[u] = 1;
for (int i = 0, nx, w; i < adj[u].size(); i++){
nx = adj[u][i].fi; w = adj[u][i].se;
if (nx == prv) continue;
dep[nx] = dep[u] + 1;
dist[nx] = dist[u] + w;
getsz(nx, u);
sz[u] += sz[nx];
if (bc[u] == -1 || sz[nx] > sz[bc[u]]) bc[u] = nx;
}
out[u] = tme;
}
int ans = 0x3f3f3f3f;
void dfs(int u, int prv, bool keep){
for (int i = 0, nx, w; i < adj[u].size(); i++){
nx = adj[u][i].fi;
if (nx == prv || nx == bc[u]) continue;
w = dist[nx] - dist[u];
dfs(nx, u, 0);
}
if (bc[u] != -1) dfs(bc[u], u, 1);
for (int i = 0, nx, w; i < adj[u].size(); i++){
nx = adj[u][i].fi;
if (nx == prv || nx == bc[u]) continue;
for (int j = in[nx]; j <= out[nx]; j++){
int x = flat[j]; long long w = dist[x] - dist[u];
if (w > k) continue;
// cout << " insert " << x << ' ' << w << '\n';
if (dep[x] < dep[sack[w]]) sack[w] = x;
}
}
sack[0] = u;
// cout << " begin calc " << u << '\n';
// for (int i = 0; i <= k; i++) cout << sack[i] << " \n"[i==k];
for (int i = in[u]; i <= out[u]; i++){
int x = flat[i]; long long w = dist[x] - dist[u];
// cout << "from " << x << " dist " << w << '\n';
if (w <= k && sack[k-w] != -1){
ans = min(ans, dep[x] + dep[sack[k-w]] - 2 * dep[u]);
}
}
if (!keep){
for (int i = in[u]; i <= out[u]; i++){
sack[dist[flat[i]] - dist[u]] = -1;
}
// cout << "clear\n";
}
// cout << "end calc " << u << '\n' << '\n';
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i = 0; i < n-1; i++){
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
memset(bc, -1, sizeof(bc));
memset(sack, -1, sizeof(sack));
// for (int i = 0; i < n; i++){
// cout << i << " : ";
// for (pii p : adj[i]) cout << '{' << p.fi << ", " << p.se << "} ";
// cout << '\n';
// }
getsz(0);
// for (int i = 0; i < n; i++){
// cout << dep[i] << ' ' << dist[i] << ",\n"[i==n-1];
// }
dfs(0, -1, 1);
if (ans == 0x3f3f3f3f) return -1;
return ans;
}
Compilation message
race.cpp: In function 'void getsz(int, int)':
race.cpp:22:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, nx, w; i < adj[u].size(); i++){
~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, bool)':
race.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, nx, w; i < adj[u].size(); i++){
~~^~~~~~~~~~~~~~~
race.cpp:37:22: warning: variable 'w' set but not used [-Wunused-but-set-variable]
for (int i = 0, nx, w; i < adj[u].size(); i++){
^
race.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, nx, w; i < adj[u].size(); i++){
~~^~~~~~~~~~~~~~~
race.cpp:44:22: warning: unused variable 'w' [-Wunused-variable]
for (int i = 0, nx, w; i < adj[u].size(); i++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 8 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 10 |
Correct |
9 ms |
9976 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 15 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 17 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 18 |
Correct |
10 ms |
9856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 8 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 10 |
Correct |
9 ms |
9976 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 15 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 17 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 18 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 19 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 8 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 10 |
Correct |
9 ms |
9976 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 15 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 17 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 18 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 19 |
Incorrect |
97 ms |
18772 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 8 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 10 |
Correct |
9 ms |
9976 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 15 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 17 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 18 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 19 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
