| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163950 |
2019-11-16T11:51:32 Z |
tushar_2658 |
Race (IOI11_race) |
C++14 |
|
35 ms |
36344 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, 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), make_pair(dis1(cur_c, x), x)));
}
for(auto i : edges[x]){
if(i.first == p)continue;
dfs1(i.first, x);
}
}
vector<int> t[maxn];
int st[maxn], ed[maxn];
int cnt = 0, root;
void centroid_euler(int x, int p){
st[x] = ++cnt;
for(auto i : t[x]){
if(i == p)continue;
centroid_euler(i, x);
}
ed[x] = cnt;
}
void build(int x, int p){
dfs(x, 0);
int c = centroid(x, 0, sub[x] / 2);
par[c] = p;
if(p == 0)root = c;
else {
t[p].push_back(c);
t[c].push_back(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);
}
}
bool inside(int x, int p){
if(st[x] >= st[p] && ed[x] <= ed[p])return 1;
return 0;
}
int query(int x){
int l = k, u = x, prev = -1;
int ret = INT_MAX;
while(x != 0){
int left = l - dis(x, u);
if(left < 0){
x = par[x];
continue;
}
vector<pair<int, pair<int, int>>>:: iterator itr = lower_bound(ms[x].begin(), ms[x].end(), make_pair(left, make_pair(-1, -1)));
if(itr == ms[x].end()){
x = par[x];
continue;
}
int idx = itr - ms[x].begin();
if(prev != -1){
while(inside(ms[x][idx].second.second, x) && idx < (int)ms[x].size()){
idx++;
}
}
if(ms[x][idx].first == left){
ret = min(ret, ms[x][idx].second.first + dis1(x, u));
}
prev = x;
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);
centroid_euler(root, root);
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 |
35 ms |
36344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
36344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
36344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
36344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
