| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 401998 | mshandilya | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
long long goal;
int min_edge;
std::vector<std::list<pair<int, int>>> adj_list;
std::vector<std::unordered_map<long long, int>> dist_keymap;
std::vector<int> subtree_size;
void dfs(int root, int parent,
int parent_centroid,
int edge_dist, long long km_dist,
std::vector<pair<long long, int>>& subtree_dist) {
if(dist_keymap[parent_centroid].count(goal-km_dist) and dist_keymap[parent_centroid][goal-km_dist]+edge_dist<min_edge)
min_edge = dist_keymap[parent_centroid][goal-km_dist]+edge_dist;
pair<long long, int> d = {km_dist, edge_dist};
subtree_dist.emplace_back(d);
subtree_size[root] = 1;
for(auto& i : adj_list[root]) {
if(i.first!=parent) {
dfs(i.first, root, parent_centroid, edge_dist+1, km_dist+i.second, subtree_dist);
subtree_size[root] += subtree_size[i.first];
}
}
return;
}
void build_tree(int root, int tree_size) {
int centroid = root;
bool found = false;
while(!found){
found = true;
for(auto& i : adj_list[centroid])
if(subtree_size[i.first]>tree_size/2) {
subtree_size[centroid] = tree_size - subtree_size[i.first];
subtree_size[i.first] = tree_size;
centroid = i.first;
found = false;
}
}
dist_keymap[centroid][0] = 0;
for(auto& child : adj_list[centroid]) {
std::list<pair<int, int>>::iterator i = adj_list[child.first].begin();
for(; i!=adj_list[child.first].end(); i++)
if((*i).first == centroid)
break;
adj_list[child.first].erase(i);
std::vector<pair<long long, int>> subtree_dist;
dfs(child.first, centroid, centroid, 1, child.second, subtree_dist);
for(auto& i : subtree_dist) {
if(!dist_keymap[centroid].count(i.first) or dist_keymap[centroid][i.first]>i.second)
dist_keymap[centroid][i.first] = i.second;
}
build_tree(child.first, subtree_size[child.first]);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
goal = K;
min_edge = N+1;
adj_list.assign(N, std::list<pair<int, int>> ());
subtree_size.resize(N);
dist_keymap.assign(N, unordered_map<long long, int> ());
for(int i = 0; i<N-1; i++) {
adj_list[H[i][0]].push_back({H[i][1], L[i]});
adj_list[H[i][1]].push_back({H[i][0], L[i]});
}
std::vector<pair<long long, int>> garbage_vector;
dfs(0, -1, 0, -N, -(long long)2e5, garbage_vector);
build_tree(0, N);
if(min_edge<n)
return min_edge;
else
return -1;
}