| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1063661 |
2024-08-17T22:31:16 Z |
kkkkkkkk |
Race (IOI11_race) |
C++14 |
|
2 ms |
13672 KB |
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > G[200005];
bool is_removed[200005];
int subtree_size[200005];
int rez=INT_MAX;
int cekori[1000005];
int k;
int get_subtree_size(int teme, int parent=-1) {
subtree_size[teme]=1;
for (auto [next, dolz]:G[teme]) {
if (next==parent||is_removed[next]) continue;
subtree_size[teme]+=get_subtree_size(next, teme);
}
return subtree_size[teme];
}
int get_centroid(int teme, int tree_size, int parent=-1) {
for (auto [next, dolz]:G[teme]) {
if (next==parent||is_removed[next]) continue;
if (subtree_size[next]*2>tree_size)
return get_centroid(next, tree_size, teme);
}
return teme;
}
queue<int> q;
void dfs1(int teme, int parent, int dolz, int depth) {
if (dolz>k) return;
if (cekori[dolz]>depth) cekori[dolz]=depth;
else if (cekori[dolz]==-1) cekori[dolz]=depth, q.push(dolz);
for (auto [next, dist]:G[teme]) {
if (next==parent||is_removed[next]) continue;
dfs1(next, teme, dolz+dist, depth+1);
}
}
void dfs2(int teme, int parent, int dolz, int depth) {
if (dolz>k) return;
if (cekori[k-dolz]!=-1)
rez=min(rez, depth+cekori[k-dolz]);
for (auto [next, dist]:G[teme]) {
if (next==parent||is_removed[next]) continue;
dfs2(next, teme, dolz+dist, depth+1);
}
}
void build_centroid_decomp(int teme=0) {
int centroid=get_centroid(teme, get_subtree_size(teme));
for (auto [next, dist]:G[centroid]) {
if (is_removed[next]) continue;
dfs2(next, centroid, dist, 1);
dfs1(next, centroid, dist, 1);
}
while (!q.empty()) {
int br=q.front();
q.pop();
cekori[br]=-1;
}
is_removed[centroid]=1;
for (auto [next, dist]:G[centroid]) {
if (is_removed[next]) continue;
build_centroid_decomp(next);
}
}
int best_path(int n, int K, int H[][2], int L[]) {
for (int i=0;i<n-1;i++) {
G[H[i][0]].push_back({H[i][1], L[i]});
G[H[i][1]].push_back({H[i][0], L[i]});
}
k=K;
memset(cekori, -1, sizeof(cekori));
build_centroid_decomp();
if (rez==INT_MAX) return -1;
return rez;
}
Compilation message
race.cpp: In function 'int get_subtree_size(int, int)':
race.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
14 | for (auto [next, dolz]:G[teme]) {
| ^
race.cpp: In function 'int get_centroid(int, int, int)':
race.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for (auto [next, dolz]:G[teme]) {
| ^
race.cpp: In function 'void dfs1(int, int, int, int)':
race.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | for (auto [next, dist]:G[teme]) {
| ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:46:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | for (auto [next, dist]:G[teme]) {
| ^
race.cpp: In function 'void build_centroid_decomp(int)':
race.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for (auto [next, dist]:G[centroid]) {
| ^
race.cpp:65:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for (auto [next, dist]:G[centroid]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
2 ms |
13672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13668 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
2 ms |
13672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13668 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
2 ms |
13672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13668 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
2 ms |
13672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13668 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
