| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 253389 |
2020-07-27T21:25:35 Z |
ChrisT |
Race (IOI11_race) |
C++17 |
|
1073 ms |
37356 KB |
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef pair<int,int> pii;
vector<pii> adj[200001],nw;
int sz[200001], ans,k;
int H[200001][2], L[200001];
bool centroid[200001];
map<int,int> mindist;
int dist[200001], len[200001];
int dfs (int cur ,int p) {
sz[cur] = 1;
for (pii i : adj[cur]) if(i.first != p && !centroid[i.first]) sz[cur] += dfs(i.first,cur);
return sz[cur];
}
void firstlength (int cur, int par, int down, int length) {
if (mindist.find(down) == mindist.end() || length < mindist[down])
mindist[down] = length;
if (down == k) ans = min(ans,length);
for (pii p : adj[cur]) if (!centroid[p.first] && p.first != par) firstlength(p.first,cur,down+p.second,length+1);
}
void findlength (int cur ,int par ,int down, int length) {
if (down == k) ans = min(ans,length);
if (mindist.find(down) == mindist.end() || mindist[down] > length) nw.push_back({down,length});
if (mindist.find(k-down) != mindist.end()) ans = min(ans,length+mindist[k-down]);
for (pii p : adj[cur]) if (!centroid[p.first] && p.first != par) findlength(p.first,cur,down+p.second,length+1);
}
int findCentroid (int cur, int p, int n) {
for (pii i : adj[cur])
if (i.first != p && !centroid[i.first] && sz[i.first] > (n>>1))
return findCentroid (i.first,cur,n);
return cur;
}
void solve (int cur) {
dfs(cur,-1);
int cent = findCentroid(cur,-1,sz[cur]);
centroid[cent] = 1;
mindist.clear();
int i;
for (i = 0; i < adj[cent].size() ; i++) if (!centroid[adj[cent][i].first]) {firstlength(adj[cent][i].first,cent,adj[cent][i].second,1); break;}
for (i++; i < adj[cent].size(); i++) if (!centroid[adj[cent][i].first]) {
findlength(adj[cent][i].first,cent,adj[cent][i].second,1);
while (!nw.empty()) mindist[nw.back().first] = nw.back().second, nw.pop_back();
}
for (pii p : adj[cent]) if (!centroid[p.first]) solve(p.first);
}
int best_path(int n, int K, int h[][2], int l[]) {
k=K;
for (int i = 0; i < n-1; i++) {
adj[h[i][0]].push_back({h[i][1],l[i]});
adj[h[i][1]].push_back({h[i][0],l[i]});
}
ans = INT_MAX;
solve(0);
return ans == INT_MAX ? -1 : ans;
}
Compilation message
race.cpp: In function 'void solve(int)':
race.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < adj[cent].size() ; i++) if (!centroid[adj[cent][i].first]) {firstlength(adj[cent][i].first,cent,adj[cent][i].second,1); break;}
~~^~~~~~~~~~~~~~~~~~
race.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i++; i < adj[cent].size(); i++) if (!centroid[adj[cent][i].first]) {
~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 21 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 24 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 25 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 26 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 27 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 28 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 29 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 30 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 31 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 32 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 33 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 34 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 35 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 36 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 37 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 38 |
Correct |
5 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 19 |
Correct |
242 ms |
11784 KB |
Output is correct |
| 20 |
Correct |
251 ms |
11968 KB |
Output is correct |
| 21 |
Correct |
227 ms |
11768 KB |
Output is correct |
| 22 |
Correct |
205 ms |
11896 KB |
Output is correct |
| 23 |
Correct |
297 ms |
12152 KB |
Output is correct |
| 24 |
Correct |
149 ms |
11896 KB |
Output is correct |
| 25 |
Correct |
187 ms |
16628 KB |
Output is correct |
| 26 |
Correct |
104 ms |
16120 KB |
Output is correct |
| 27 |
Correct |
323 ms |
18936 KB |
Output is correct |
| 28 |
Correct |
864 ms |
37228 KB |
Output is correct |
| 29 |
Correct |
864 ms |
37228 KB |
Output is correct |
| 30 |
Correct |
333 ms |
18996 KB |
Output is correct |
| 31 |
Correct |
329 ms |
19040 KB |
Output is correct |
| 32 |
Correct |
385 ms |
19236 KB |
Output is correct |
| 33 |
Correct |
511 ms |
17912 KB |
Output is correct |
| 34 |
Correct |
943 ms |
28396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 21 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 24 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 25 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 26 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 27 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 28 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 29 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 30 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 31 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 32 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 33 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 34 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 35 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 36 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 37 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 38 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 39 |
Correct |
242 ms |
11784 KB |
Output is correct |
| 40 |
Correct |
251 ms |
11968 KB |
Output is correct |
| 41 |
Correct |
227 ms |
11768 KB |
Output is correct |
| 42 |
Correct |
205 ms |
11896 KB |
Output is correct |
| 43 |
Correct |
297 ms |
12152 KB |
Output is correct |
| 44 |
Correct |
149 ms |
11896 KB |
Output is correct |
| 45 |
Correct |
187 ms |
16628 KB |
Output is correct |
| 46 |
Correct |
104 ms |
16120 KB |
Output is correct |
| 47 |
Correct |
323 ms |
18936 KB |
Output is correct |
| 48 |
Correct |
864 ms |
37228 KB |
Output is correct |
| 49 |
Correct |
864 ms |
37228 KB |
Output is correct |
| 50 |
Correct |
333 ms |
18996 KB |
Output is correct |
| 51 |
Correct |
329 ms |
19040 KB |
Output is correct |
| 52 |
Correct |
385 ms |
19236 KB |
Output is correct |
| 53 |
Correct |
511 ms |
17912 KB |
Output is correct |
| 54 |
Correct |
943 ms |
28396 KB |
Output is correct |
| 55 |
Correct |
27 ms |
5984 KB |
Output is correct |
| 56 |
Correct |
16 ms |
5760 KB |
Output is correct |
| 57 |
Correct |
161 ms |
12156 KB |
Output is correct |
| 58 |
Correct |
52 ms |
11628 KB |
Output is correct |
| 59 |
Correct |
298 ms |
19572 KB |
Output is correct |
| 60 |
Correct |
898 ms |
36460 KB |
Output is correct |
| 61 |
Correct |
397 ms |
20476 KB |
Output is correct |
| 62 |
Correct |
309 ms |
19064 KB |
Output is correct |
| 63 |
Correct |
429 ms |
19192 KB |
Output is correct |
| 64 |
Correct |
1042 ms |
24052 KB |
Output is correct |
| 65 |
Correct |
1073 ms |
29300 KB |
Output is correct |
| 66 |
Correct |
938 ms |
37356 KB |
Output is correct |
| 67 |
Correct |
154 ms |
19680 KB |
Output is correct |
| 68 |
Correct |
559 ms |
28308 KB |
Output is correct |
| 69 |
Correct |
560 ms |
28668 KB |
Output is correct |
| 70 |
Correct |
483 ms |
27368 KB |
Output is correct |
