| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163945 |
2019-11-16T11:20:32 Z |
tushar_2658 |
Race (IOI11_race) |
C++14 |
|
32 ms |
31608 KB |
#include "bits/stdc++.h"
using namespace std;
const int maxn = 200005;
int n, k;
set<pair<int, int>> edges[maxn];
int sub[maxn], par[maxn], d[maxn], dp[maxn][22], depth[maxn];
void rem(pair<int, int> x, int y){
edges[y].erase(x);
edges[x.first].erase(make_pair(y, x.second));
}
void dfs(int x, int p){
sub[x] = 1;
for(auto i : edges[x]){
if(i.first == p)continue;
dfs(i.first, x);
sub[x] += sub[i.first];
}
}
int centroid(int x, int p, int range){
for(auto i : edges[x]){
if(i.first == p)continue;
if(sub[i.first] > range)return centroid(i.first, x, range);
}return x;
}
vector<pair<int, int>> ms[maxn];
int cur_c;
void get(int x, int p, int dd){
dp[x][0] = p;
depth[x] = depth[p] + 1;
d[x] = d[p] + dd;
for(auto i : edges[x]){
if(i.first == p)continue;
get(i.first, x, i.second);
}
}
int lca(int x, int y){
if(depth[x] < depth[y])swap(x, y);
for(int i = 21; i >= 0; i--){
if(depth[x] - (1 << i) >= depth[y]){
x = dp[x][i];
}
}
if(x == y)return x;
for(int i = 21; i >= 0; i--){
if(dp[x][i] != dp[y][i] && dp[x][i] != -1 && dp[y][i] != -1){
x = dp[x][i];
y = dp[y][i];
}
}
return dp[x][0];
}
int dis(int x, int y){
return d[x] + d[y] - 2 * d[lca(x, y)];
}
int dis1(int x, int y){
return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}
void dfs1(int x, int p){
if(cur_c != x){
ms[cur_c].push_back(make_pair(dis(cur_c, x), dis1(cur_c, x)));
}
for(auto i : edges[x]){
if(i.first == p)continue;
dfs1(i.first, x);
}
}
void build(int x, int p){
dfs(x, 0);
int c = centroid(x, 0, sub[x] / 2);
par[c] = p;
cur_c = c;
dfs1(c, p);
sort(ms[cur_c].begin(), ms[cur_c].end());
vector<pair<int, int>> v;
copy(edges[c].begin(), edges[c].end(), back_inserter(v));
for(auto i : v){
rem(i, c);
build(i.first, c);
}
}
int query(int x){
int l = k, u = x;
int ret = INT_MAX;
while(x != 0){
int left = l - dis(x, u);
if(left < 0){
x = par[x];
continue;
}
int lo = 0, hi = ms[x].size() - 1, ans = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(ms[x][mid].first >= left){
ans = mid;
hi = mid - 1;
}else {
lo = mid + 1;
}
}
if(ans == -1){
x = par[x];
continue;
}
if(ms[x][ans].first == left){
ret = min(ret, ms[x][ans].second + dis1(x, u));
}
x = par[x];
}return ret;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for(int i = 0; i < n - 1; i++){
edges[H[i][0] + 1].insert(make_pair(H[i][1] + 1, L[i]));
edges[H[i][1] + 1].insert(make_pair(H[i][0] + 1, L[i]));
}
memset(dp, -1, sizeof dp);
get(1, 0, 0);
for(int j = 1; j < 22; j++){
for(int i = 1; i <= n; i++){
if(dp[i][j - 1] != -1){
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
build(1, 0);
int ans = INT_MAX;
for(int i = 1; i <= n; i++){
ans = min(ans, query(i));
}
return (ans >= INT_MAX ? -1 : ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
31608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
31608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
31608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
31608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
