| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 71491 |
2018-08-24T23:04:57 Z |
RezwanArefin01 |
Race (IOI11_race) |
C++17 |
|
2109 ms |
114532 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 2e5 + 10;
vector<int> adj[maxn], cost[maxn];
ll dist[maxn]; bool vis[maxn];
int sub[maxn], len[maxn], n, k;
int ans = 1e9;
void calc(int u, int par) {
sub[u] = 1;
for(int v : adj[u]) if(v - par && !vis[v])
calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
for(int v : adj[u]) if(v - par && !vis[v])
if(sub[v] > r) return centroid(v, u, r);
return u;
}
vector<int> vert; int in[maxn], out[maxn];
void dfs(int u, int par) {
in[u] = vert.size(); vert.push_back(u);
for(int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i], c = cost[u][i];
if(v == par || vis[v]) continue;
dist[v] = dist[u] + c;
len[v] = len[u] + 1;
dfs(v, u);
} out[u] = vert.size() - 1;
}
void solve(int u) {
dist[u] = len[u] = 0;
vert.clear(); dfs(u, -1);
unordered_map<ll, int> mp; mp[0] = 0;
for(int v : adj[u]) if(!vis[v]) {
for(int t = in[v]; t <= out[v]; ++t) {
int w = vert[t];
if(mp.count(k - dist[w]))
ans = min(ans, mp[k - dist[w]] + len[w]);
}
for(int t = in[v]; t <= out[v]; ++t) {
int w = vert[t];
if(!mp.count(dist[w])) mp[dist[w]] = len[w];
else mp[dist[w]] = min(mp[dist[w]], len[w]);
}
}
}
void decomp(int u, int par) {
calc(u, -1);
int c = centroid(u, par, sub[u] / 2);
solve(c); vis[c] = 1;
for(int v : adj[c]) if(!vis[v]) decomp(v, c);
}
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]].push_back(H[i][1]);
adj[H[i][1]].push_back(H[i][0]);
cost[H[i][0]].push_back(L[i]);
cost[H[i][1]].push_back(L[i]);
}
decomp(0, -1);
if(ans == 1e9) ans = -1;
return ans;
}
Compilation message
race.cpp: In function 'void dfs(int, int)':
race.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); ++i) {
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9956 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9988 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9996 KB |
Output is correct |
| 5 |
Correct |
13 ms |
9996 KB |
Output is correct |
| 6 |
Correct |
10 ms |
10056 KB |
Output is correct |
| 7 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 8 |
Correct |
15 ms |
10108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10108 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 11 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 12 |
Correct |
14 ms |
10172 KB |
Output is correct |
| 13 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 14 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 15 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 16 |
Correct |
13 ms |
10172 KB |
Output is correct |
| 17 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 18 |
Correct |
13 ms |
10248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9956 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9988 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9996 KB |
Output is correct |
| 5 |
Correct |
13 ms |
9996 KB |
Output is correct |
| 6 |
Correct |
10 ms |
10056 KB |
Output is correct |
| 7 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 8 |
Correct |
15 ms |
10108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10108 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 11 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 12 |
Correct |
14 ms |
10172 KB |
Output is correct |
| 13 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 14 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 15 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 16 |
Correct |
13 ms |
10172 KB |
Output is correct |
| 17 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 18 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 19 |
Correct |
12 ms |
10248 KB |
Output is correct |
| 20 |
Correct |
12 ms |
10248 KB |
Output is correct |
| 21 |
Correct |
14 ms |
10264 KB |
Output is correct |
| 22 |
Correct |
15 ms |
10404 KB |
Output is correct |
| 23 |
Correct |
16 ms |
10404 KB |
Output is correct |
| 24 |
Correct |
16 ms |
10468 KB |
Output is correct |
| 25 |
Correct |
13 ms |
10500 KB |
Output is correct |
| 26 |
Correct |
13 ms |
10532 KB |
Output is correct |
| 27 |
Correct |
16 ms |
10532 KB |
Output is correct |
| 28 |
Correct |
16 ms |
10532 KB |
Output is correct |
| 29 |
Correct |
14 ms |
10532 KB |
Output is correct |
| 30 |
Correct |
16 ms |
10532 KB |
Output is correct |
| 31 |
Correct |
15 ms |
10532 KB |
Output is correct |
| 32 |
Correct |
14 ms |
10532 KB |
Output is correct |
| 33 |
Correct |
15 ms |
10540 KB |
Output is correct |
| 34 |
Correct |
13 ms |
10540 KB |
Output is correct |
| 35 |
Correct |
15 ms |
10548 KB |
Output is correct |
| 36 |
Correct |
15 ms |
10560 KB |
Output is correct |
| 37 |
Correct |
14 ms |
10572 KB |
Output is correct |
| 38 |
Correct |
14 ms |
10584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9956 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9988 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9996 KB |
Output is correct |
| 5 |
Correct |
13 ms |
9996 KB |
Output is correct |
| 6 |
Correct |
10 ms |
10056 KB |
Output is correct |
| 7 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 8 |
Correct |
15 ms |
10108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10108 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 11 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 12 |
Correct |
14 ms |
10172 KB |
Output is correct |
| 13 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 14 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 15 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 16 |
Correct |
13 ms |
10172 KB |
Output is correct |
| 17 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 18 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 19 |
Correct |
524 ms |
22368 KB |
Output is correct |
| 20 |
Correct |
440 ms |
23716 KB |
Output is correct |
| 21 |
Correct |
518 ms |
25192 KB |
Output is correct |
| 22 |
Correct |
423 ms |
26648 KB |
Output is correct |
| 23 |
Correct |
631 ms |
27852 KB |
Output is correct |
| 24 |
Correct |
260 ms |
29908 KB |
Output is correct |
| 25 |
Correct |
651 ms |
34012 KB |
Output is correct |
| 26 |
Correct |
246 ms |
38288 KB |
Output is correct |
| 27 |
Correct |
604 ms |
46480 KB |
Output is correct |
| 28 |
Correct |
1760 ms |
68344 KB |
Output is correct |
| 29 |
Correct |
1684 ms |
70404 KB |
Output is correct |
| 30 |
Correct |
568 ms |
70404 KB |
Output is correct |
| 31 |
Correct |
565 ms |
70404 KB |
Output is correct |
| 32 |
Correct |
723 ms |
70404 KB |
Output is correct |
| 33 |
Correct |
1030 ms |
70404 KB |
Output is correct |
| 34 |
Correct |
1660 ms |
74624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9956 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9988 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9996 KB |
Output is correct |
| 5 |
Correct |
13 ms |
9996 KB |
Output is correct |
| 6 |
Correct |
10 ms |
10056 KB |
Output is correct |
| 7 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 8 |
Correct |
15 ms |
10108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10108 KB |
Output is correct |
| 10 |
Correct |
12 ms |
10108 KB |
Output is correct |
| 11 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 12 |
Correct |
14 ms |
10172 KB |
Output is correct |
| 13 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 14 |
Correct |
11 ms |
10172 KB |
Output is correct |
| 15 |
Correct |
12 ms |
10172 KB |
Output is correct |
| 16 |
Correct |
13 ms |
10172 KB |
Output is correct |
| 17 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 18 |
Correct |
13 ms |
10248 KB |
Output is correct |
| 19 |
Correct |
12 ms |
10248 KB |
Output is correct |
| 20 |
Correct |
12 ms |
10248 KB |
Output is correct |
| 21 |
Correct |
14 ms |
10264 KB |
Output is correct |
| 22 |
Correct |
15 ms |
10404 KB |
Output is correct |
| 23 |
Correct |
16 ms |
10404 KB |
Output is correct |
| 24 |
Correct |
16 ms |
10468 KB |
Output is correct |
| 25 |
Correct |
13 ms |
10500 KB |
Output is correct |
| 26 |
Correct |
13 ms |
10532 KB |
Output is correct |
| 27 |
Correct |
16 ms |
10532 KB |
Output is correct |
| 28 |
Correct |
16 ms |
10532 KB |
Output is correct |
| 29 |
Correct |
14 ms |
10532 KB |
Output is correct |
| 30 |
Correct |
16 ms |
10532 KB |
Output is correct |
| 31 |
Correct |
15 ms |
10532 KB |
Output is correct |
| 32 |
Correct |
14 ms |
10532 KB |
Output is correct |
| 33 |
Correct |
15 ms |
10540 KB |
Output is correct |
| 34 |
Correct |
13 ms |
10540 KB |
Output is correct |
| 35 |
Correct |
15 ms |
10548 KB |
Output is correct |
| 36 |
Correct |
15 ms |
10560 KB |
Output is correct |
| 37 |
Correct |
14 ms |
10572 KB |
Output is correct |
| 38 |
Correct |
14 ms |
10584 KB |
Output is correct |
| 39 |
Correct |
524 ms |
22368 KB |
Output is correct |
| 40 |
Correct |
440 ms |
23716 KB |
Output is correct |
| 41 |
Correct |
518 ms |
25192 KB |
Output is correct |
| 42 |
Correct |
423 ms |
26648 KB |
Output is correct |
| 43 |
Correct |
631 ms |
27852 KB |
Output is correct |
| 44 |
Correct |
260 ms |
29908 KB |
Output is correct |
| 45 |
Correct |
651 ms |
34012 KB |
Output is correct |
| 46 |
Correct |
246 ms |
38288 KB |
Output is correct |
| 47 |
Correct |
604 ms |
46480 KB |
Output is correct |
| 48 |
Correct |
1760 ms |
68344 KB |
Output is correct |
| 49 |
Correct |
1684 ms |
70404 KB |
Output is correct |
| 50 |
Correct |
568 ms |
70404 KB |
Output is correct |
| 51 |
Correct |
565 ms |
70404 KB |
Output is correct |
| 52 |
Correct |
723 ms |
70404 KB |
Output is correct |
| 53 |
Correct |
1030 ms |
70404 KB |
Output is correct |
| 54 |
Correct |
1660 ms |
74624 KB |
Output is correct |
| 55 |
Correct |
41 ms |
74624 KB |
Output is correct |
| 56 |
Correct |
34 ms |
74624 KB |
Output is correct |
| 57 |
Correct |
275 ms |
74624 KB |
Output is correct |
| 58 |
Correct |
99 ms |
74624 KB |
Output is correct |
| 59 |
Correct |
408 ms |
74624 KB |
Output is correct |
| 60 |
Correct |
1846 ms |
92924 KB |
Output is correct |
| 61 |
Correct |
638 ms |
92924 KB |
Output is correct |
| 62 |
Correct |
613 ms |
92924 KB |
Output is correct |
| 63 |
Correct |
826 ms |
92924 KB |
Output is correct |
| 64 |
Correct |
1502 ms |
92924 KB |
Output is correct |
| 65 |
Correct |
1400 ms |
98272 KB |
Output is correct |
| 66 |
Correct |
2109 ms |
110780 KB |
Output is correct |
| 67 |
Correct |
542 ms |
110780 KB |
Output is correct |
| 68 |
Correct |
872 ms |
110780 KB |
Output is correct |
| 69 |
Correct |
932 ms |
112424 KB |
Output is correct |
| 70 |
Correct |
902 ms |
114532 KB |
Output is correct |
