| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 552797 | Olympia | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <climits>
#include "race.h"
using namespace std;
class Tree {
public:
vector<vector<int>> adj;
map<pair<int,int>,int> weight;
vector<bool> hasVisited;
vector<int> sub;
int sz = 0;
int dfs_for_sz (int curNode, int prevNode) {
sub[curNode] = 1;
for (int i: adj[curNode]) {
if (i != prevNode && !hasVisited[i]) {
sub[curNode] += dfs_for_sz (i, curNode);
}
}
return (sz = sub[curNode]);
}
int find_centroid (int curNode, int prevNode) {
for (int i: adj[curNode]) {
if (sub[i] * 2 > sz && !hasVisited[i] && i != prevNode) {
return find_centroid(i, curNode);
}
}
return curNode;
}
map<int,int> tot, exc;
void dfs (int curNode, int prevNode, int w, int d) {
if (exc.count(w)) exc[w] = min(exc[w], d);
else exc[w] = d;
for (int i: adj[curNode]) {
if (i != prevNode && !hasVisited[i]) {
dfs (i, curNode, w + weight[make_pair(i, curNode)], d + 1);
}
}
}
int ans = INT_MAX;
int k;
void solve (int curNode) {
dfs_for_sz(curNode, curNode);
int centroid = find_centroid(curNode, curNode);
hasVisited[centroid] = true;
//Two Cases:
//(1) It passes through the centroid
//(2) It doesn't pass through the centroid
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
dfs (i, i, weight[make_pair(i, centroid)], 1);
for (auto& p: exc) {
if (tot.count(k - p.first)) {
ans = min(ans, tot[k - p.first] + p.second);
}
}
for (auto& p: exc) {
if (tot.count(p.first)) tot[p.first] = min(tot[p.first], p.second);
else tot[p.first] = p.second;
}
exc.clear();
}
}
if (tot.count(k)) {
ans = min(ans, tot[k]);
}
tot.clear();
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
solve (i);
}
}
}
void add_weight (int u, int v, int w) {
weight[make_pair(u, v)] = weight[make_pair(v, u)] = w;
adj[u].push_back(v), adj[v].push_back(u);
}
Tree (int n, int k) {
adj.resize(n), hasVisited.assign(n, false), sub.assign(n, false);
this->k = k;
}
};
int best_path(int n, int k, int H[][2], int L[]){
::n=n; ::k=k;
Tree myTree(n, k);
for (int i = 0; i < n - 1; i++) {
myTree.add_edge(H[i][0], H[i][1], L[i]);
}
myTree.solve(0);
return myTree.ans;
}
/*
int main() {
int N, K;
cin >> N >> K;
Tree myTree(N, K);
for (int i = 0; i < N - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
myTree.add_weight(u, v, w);
}
}
*/