| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 992230 |
2024-06-04T07:02:33 Z |
Alfraganus |
Race (IOI11_race) |
C++17 |
|
1 ms |
2392 KB |
#include "race.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define printmp(a) for(auto x : a) cout << x.first << ' ' << x.second << endl;
vector<vector<array<int, 2>>> graph;
vector<int> subtree_size;
vector<bool> removed, used;
struct Centroid_Decomposition{
void sub_size(int node, int par){
subtree_size[node] = 1;
for(auto &child : graph[node]){
if(child[0] != par and !removed[child[0]]){
sub_size(child[0], node);
subtree_size[node] += subtree_size[child[0]];
}
}
}
int center(int node, int par, int size){
for(auto [x, y] : graph[node]){
if(x != par and !removed[x]){
if(subtree_size[x] * 2 > size)
return center(x, node, size);
}
}
return node;
}
int find_center(int node){
sub_size(node, -1);
return center(node, -1, subtree_size[node]);
}
int dfs(int node, int k){
int x = find_center(node);
removed[x] = true;
int ans = 1e9;
map<int, int> mp;
mp[0] = 0;
for(auto y : graph[x]){
if(!removed[y[0]] and y[1] <= k){
queue<array<int, 3>> q;
q.push({y[0], y[1], 1});
used[y[0]] = 1;
while(!q.empty()){
array<int, 3> cur = q.front();
q.pop();
if(mp.count(k - cur[1]) == 1)
ans = min(ans, mp[k - cur[1]] + cur[2]);
for(auto x : graph[cur[0]]){
if(!used[x[0]] and !removed[x[0]] and cur[1] + x[1] <= k){
q.push({x[0], cur[1] + x[1], x[2] + 1});
used[x[0]] = 1;
}
}
}
q.push({y[0], y[1], 1});
used[y[0]] = 0;
while(!q.empty()){
array<int, 3> cur = q.front();
q.pop();
if(mp.count(cur[1]) == 0)
mp[cur[1]] = cur[2];
else
mp[cur[1]] = min(mp[cur[1]], cur[2]);
for(auto x : graph[cur[0]]){
if(used[x[0]] and !removed[x[0]] and cur[1] + x[1] <= k){
q.push({x[0], cur[1] + x[1], x[2] + 1});
used[x[0]] = 0;
}
}
}
}
}
for(auto y : graph[x])
if(!removed[y[0]])
ans = min(ans, dfs(y[0], k));
return ans;
}
int get(int k){
return dfs(0, k);
}
};
int best_path(int n, int k, int h[][2], int l[]){
graph.resize(n);
subtree_size.resize(n);
removed.resize(n);
used.resize(n);
for(int i = 0; i < n - 1; i++){
graph[h[i][0]].push_back({h[i][1], l[i]});
graph[h[i][1]].push_back({h[i][0], l[i]});
}
Centroid_Decomposition cd;
int ans = cd.get(k);
if(ans == 1e9)
return -1;
return ans;
}
Compilation message
race.cpp: In function 'int Centroid_Decomposition::dfs(int, int)':
race.cpp:76:49: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
76 | q.push({x[0], cur[1] + x[1], x[2] + 1});
race.cpp:74:20: note: while referencing 'x'
74 | for(auto x : graph[cur[0]]){
| ^
race.cpp:58:49: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
58 | q.push({x[0], cur[1] + x[1], x[2] + 1});
race.cpp:56:20: note: while referencing 'x'
56 | for(auto x : graph[cur[0]]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
