| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1270010 | pedro | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define INF 99999999999999
#define length second
ll n, k, bestSol = INF;
vector<vector<pair<int, ll>>> adj; // node -> {node, length}
vector<pair<int, ll>> smallest; // [lenght] -> {flag, edgeCount}
vector<pair<int, ll>> nodeInfo; // node -> {edgeCount, length}
vi sizes;
vector<bool> wasRoot;
int centroid;
int flag = 0;
void dfs1(int node, int parent, int edgeCount, ll lenSum) {
nodeInfo[node] = {edgeCount, lenSum};
if (lenSum > k) return;
ll s = smallest[k-lenSum].first == flag ? smallest[k-lenSum].second : INF;
if (k - lenSum >= 0 && s + edgeCount < bestSol) {
bestSol = smallest[k-lenSum].second + edgeCount;
}
for (auto child : adj[node]) if (child.first != parent && !wasRoot[child.first])
dfs1(child.first, node, edgeCount + 1, lenSum + child.second);
}
void dfs2(int node, int parent) {
pair<int, ll> info = nodeInfo[node];
if (info.length > k) return;
if (smallest[info.length].first != flag || smallest[info.length].second > info.first) {
smallest[info.length].first = flag;
smallest[info.length].second = info.first;
}
for (auto child : adj[node]) if (child.first != parent && !wasRoot[child.first])
dfs2(child.first, node);
}
void subtreeSize(int node, int parent) {
int s = 1;
for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != parent && !wasRoot[adj[node][i].first]) {
subtreeSize(adj[node][i].first, node);
s += sizes[adj[node][i].first];
}
sizes[node] = s;
}
void findCentroid(int node, int parent, int numVert) {
centroid = node;
ii max = { -1, -1 }; // val, node;
bool isCentroid = true;
for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != parent && !wasRoot[adj[node][i].first]) {
if (sizes[adj[node][i].first] > max.first) max = { sizes[adj[node][i].first], adj[node][i].first };
if (sizes[adj[node][i].first] > numVert / 2) isCentroid = false;
}
if (!isCentroid) {
sizes[node] = numVert - sizes[node] + 1;
findCentroid(max.second, node, numVert);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
adj = vector<vector<pair<int, ll>>>(n);
smallest = vector<pair<int, ll>>(1000001, {0, INF});
for (int i=0; i<n-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
nodeInfo = vector<ii>(n, {-1, -1});
queue<int> queue;
wasRoot = vector<bool>(n, false);
sizes = vi(n, 0);
queue.push(0);
while (!queue.empty()) {
int currRoot = queue.front();
//sizes = vi(n, 0);
subtreeSize(currRoot, -1);
int numVertSubTree = sizes[currRoot];
findCentroid(currRoot, -1, numVertSubTree);
currRoot = centroid;
wasRoot[currRoot] = true;
smallest[0] = {flag, 0};
queue.pop();
for (auto child : adj[currRoot]) if (!wasRoot[child.first]) {
queue.push(child.first);
dfs1(child.first, currRoot, 1, child.second);
dfs2(child.first, currRoot);
}
flag++;
}
if (bestSol == INF) return -1;
else return bestSol;
}