| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 132496 |
2019-07-19T04:47:06 Z |
socho |
Race (IOI11_race) |
C++14 |
|
3000 ms |
12208 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int n, targ;
vector<pair<int, int> > adj[200005]; // other, dist
bool vis[200005];
pair<int, int> dstore[200005];
void dfs(int node, int dist, int paths) {
// dist: current distance, paths: num paths
vis[node] = true;
for (int i=0; i<adj[node].size(); i++) {
int cons = adj[node][i].first;
if (!vis[cons]) {
dfs(cons, dist+adj[node][i].second, paths+1);
}
}
dstore[node] = make_pair(dist, paths);
}
int getbest(int s) {
memset(vis, 0, sizeof vis);
dfs(s, 0, 0);
int best = INT_MAX;
bool can = false;
for (int i=0; i<n; i++) {
if (dstore[i].first == targ) {
can = true;
best = min(best, dstore[i].second);
}
}
if (best == INT_MAX) return -1;
return best;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
targ = K;
for (int i=0; i<n-1; i++) {
int a = H[i][0];
int b = H[i][1];
int l = L[i];
adj[a].push_back(make_pair(b, l));
adj[b].push_back(make_pair(a, l));
}
bool can = false;
int best = INT_MAX;
for (int source = 0; source < N; source++) {
int res = getbest(source);
if (res != -1) {
can = true;
best = min(best, res);
}
}
if (!can) return -1;
return best;
}
Compilation message
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:13:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<adj[node].size(); i++) {
~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int getbest(int)':
race.cpp:26:7: warning: variable 'can' set but not used [-Wunused-but-set-variable]
bool can = false;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5372 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 14 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5368 KB |
Output is correct |
| 18 |
Correct |
7 ms |
5240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5372 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 14 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5368 KB |
Output is correct |
| 18 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 19 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 20 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 21 |
Correct |
32 ms |
5340 KB |
Output is correct |
| 22 |
Correct |
35 ms |
5368 KB |
Output is correct |
| 23 |
Correct |
34 ms |
5368 KB |
Output is correct |
| 24 |
Correct |
33 ms |
5376 KB |
Output is correct |
| 25 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 26 |
Correct |
32 ms |
5240 KB |
Output is correct |
| 27 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 28 |
Correct |
32 ms |
5240 KB |
Output is correct |
| 29 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 30 |
Correct |
32 ms |
5340 KB |
Output is correct |
| 31 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 32 |
Correct |
33 ms |
5496 KB |
Output is correct |
| 33 |
Correct |
33 ms |
5240 KB |
Output is correct |
| 34 |
Correct |
29 ms |
5240 KB |
Output is correct |
| 35 |
Correct |
28 ms |
5240 KB |
Output is correct |
| 36 |
Correct |
26 ms |
5240 KB |
Output is correct |
| 37 |
Correct |
26 ms |
5240 KB |
Output is correct |
| 38 |
Correct |
29 ms |
5240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5372 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 14 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5368 KB |
Output is correct |
| 18 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 19 |
Execution timed out |
3019 ms |
12208 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5372 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 14 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5368 KB |
Output is correct |
| 18 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 19 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 20 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 21 |
Correct |
32 ms |
5340 KB |
Output is correct |
| 22 |
Correct |
35 ms |
5368 KB |
Output is correct |
| 23 |
Correct |
34 ms |
5368 KB |
Output is correct |
| 24 |
Correct |
33 ms |
5376 KB |
Output is correct |
| 25 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 26 |
Correct |
32 ms |
5240 KB |
Output is correct |
| 27 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 28 |
Correct |
32 ms |
5240 KB |
Output is correct |
| 29 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 30 |
Correct |
32 ms |
5340 KB |
Output is correct |
| 31 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 32 |
Correct |
33 ms |
5496 KB |
Output is correct |
| 33 |
Correct |
33 ms |
5240 KB |
Output is correct |
| 34 |
Correct |
29 ms |
5240 KB |
Output is correct |
| 35 |
Correct |
28 ms |
5240 KB |
Output is correct |
| 36 |
Correct |
26 ms |
5240 KB |
Output is correct |
| 37 |
Correct |
26 ms |
5240 KB |
Output is correct |
| 38 |
Correct |
29 ms |
5240 KB |
Output is correct |
| 39 |
Execution timed out |
3019 ms |
12208 KB |
Time limit exceeded |
| 40 |
Halted |
0 ms |
0 KB |
- |
