¡Hola!
Estaba intentando resolver el problema Construyendo Subterráneos del OIAJ. La cosa es que me da WA en 8 de los casos y no se por qué jajaja. Ya hice varios casos a mano y el programa devuelve el resultado correcto. Me gustaría que alguien me diga qué está mal (ya sea la idea, interpretación o código).
Mi idea fue ir tomando las hojas del arbol e ir metiéndome adentro y, si al siguiente le entraban {K - 1} hojas (siendo {K} la cantidad de vecinos) se convertía en hoja. Para siempre intentar llegar con la menor distancia posible, se metía en un priority_queue que siempre me tome el avance con menor peso posible y luego de hacer cada avance, si este es mayor que el que ya teníamos, lo actualizamos y se lo restamos al peso total del árbol. Todo esto se repite mientras que el peso del árbol es mayor al presupesto.
Código
#include<bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < n; i++)
#define forit(i, a, n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, ll> arista;
struct estacion{
int u, it;
ll p;
bool operator <(const estacion &b) const{
return p >= b.p;
}
};
const int NODOS = 1000;
int main(){
//ifstream cin("subte.in");
//ofstream cout("subte.out");
vector<arista> g[NODOS];
int llegadas[NODOS];
bool vis[NODOS];
ll maxima[NODOS];
memset(llegadas, 0, sizeof(llegadas));
memset(vis, false, sizeof(vis));
memset(maxima, 0, sizeof(maxima));
int n, m, a, b, it, t;
ll c, d, sum = 0, res = 0;
cin>>n>>d;
m = n - 1;
forn(i, m){
cin>>a>>b>>c;
g[a].push_back({b, c});
g[b].push_back({a, c});
sum += c;
llegadas[a]++;
llegadas[b]++;
}
estacion u;
priority_queue<estacion> sky;
forit(i, 1, n){
if(llegadas[i] == 1){
u.u = i;
u.it = 0;
u.p = g[i][0].second;
sky.push(u);
}
}
while(sky.size() && sum > d){
u = sky.top();
sky.pop();
a = u.u;
vis[a] = true;
it = u.it;
b = g[a][it].first;
c = u.p;
maxima[b] = max(maxima[b], c);
res = c;
sum -= g[a][it].second;
llegadas[b]--;
if(llegadas[b] == 1){
a = b;
t = g[a].size();
u.u = a;
u.it = -1;
forn(i, t){
b = g[a][i].first;
if(vis[b]) continue;
c = g[a][i].second;
u.it = i;
u.p = maxima[a] + c;
break;
}
sky.push(u);
}
}
cout<<res<<endl;
return 0;
}
Espero que alguien pueda resolverme la duda.