| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1271702 | ian_otoni | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define INF 999999999
vector<vector<pair<int, int>>> adj;
vector<bool> is_removed;
vector<pair<int, int>> melhor;
int ans = INF;
int flag = 1;
int calcula_tam_subarvores(int nodo, int pai, vector<int> &sub){
sub[nodo] = 1;
for(auto &p : adj[nodo]){
int filho = p.first;
if(filho!=pai && !is_removed[filho]) sub[nodo] += calcula_tam_subarvores(filho, nodo, sub);
}
return sub[nodo];
}
int acha_centroide(int nodo, int pai, int n, vector<int> &sub){
for(auto &p : adj[nodo]){
int filho = p.first;
if(filho!=pai && !is_removed[filho] && sub[filho]>n/2) return acha_centroide(filho, nodo, n, sub);
}
return nodo;
}
void dfs1(int start_node, int parent_node, int k){
stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso
int initial_weight = 0;
for(auto &edge : adj[start_node]){
if(edge.first==parent_node){
initial_weight = edge.second;
break;
}
}
st.push(make_tuple(start_node, parent_node, 1, initial_weight)); //coloca determinado filho do centroide na pilha
while(!st.empty()){
int node, pai, distancia_da_raiz, peso_ate_araiz;
tie(node, pai, distancia_da_raiz, peso_ate_araiz) = st.top(); st.pop();
//precisamos ver se existe caminho de custo k-peso_ate_araiz que termina na raiz atual
int weight_needed = k-peso_ate_araiz;
if(weight_needed>=0 && weight_needed<melhor.size()){ //nao negativo
if(melhor[weight_needed].second==flag){
ans = min(ans, melhor[weight_needed].first+distancia_da_raiz);
}
}
//agora colocar os filhos na pilha
for(auto &p:adj[node]){
int filho = p.first;
if(filho!=pai && !is_removed[filho]){
st.push(make_tuple(filho, node, distancia_da_raiz+1, peso_ate_araiz+p.second));
}
}
}
}
void dfs2(int start_node, int parent_node, int k){
stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso
int initial_weight = 0;
for(auto &edge : adj[start_node]){
if(edge.first==parent_node){
initial_weight = edge.second;
break;
}
}
st.push(make_tuple(start_node, parent_node, 1, initial_weight)); //coloca determinado filho do centroide na pilha
while(!st.empty()){
int node, pai, distancia_da_raiz, peso_ate_araiz;
tie(node, pai, distancia_da_raiz, peso_ate_araiz) = st.top(); st.pop();
if(peso_ate_araiz<0 || peso_ate_araiz>k){
continue;
}
//salva os caminhos que comecam na raiz e terminam em vertices dessa subarvore
if(melhor[peso_ate_araiz].second==flag){
melhor[peso_ate_araiz].first = min(melhor[peso_ate_araiz].first, distancia_da_raiz);
}else{ //primeira vez que este peso aparece
melhor[peso_ate_araiz] = {distancia_da_raiz, flag};
}
//agora colocar os filhos na pilha
for(auto &p:adj[node]){
int filho = p.first;
if(filho!=pai && !is_removed[filho]){
st.push(make_tuple(filho, node, distancia_da_raiz+1, peso_ate_araiz+p.second));
}
}
}
}
void resolve(int nodo, int k){
vector<int> sub(adj.size(), 0);
calcula_tam_subarvores(nodo, -1, sub);
int centroid = acha_centroide(nodo, -1, sub[nodo], sub);
melhor[0] = {0, flag}; //so fica no centroid e nao anda
for(auto &p : adj[centroid]){
int filho = p.first;
if (!is_removed[filho]){
dfs1(filho, centroid, k);
dfs2(filho, centroid, k);
}
}
is_removed[centroid] = true;
flag++;
for(auto &p : adj[centroid]){
int filho = p.first;
if(!is_removed[filho]){
resolve(filho, k);
}
}
return;
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = INF;
flag = 1;
adj.assign(N);
is_removed.assign(N, false);
melhor.assign(K+10, {0, 0});
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
resolve(0, K);
if(ans == INF){
return -1;
}else{
return ans;
}
}