Centar za edukaciju-BiH

Čuvari galaksije - Epizoda 1 (cuvariep1)
Tehnologija je napredovala i zahvaljujudi neiscrpivim jezerima energije pronađenim na rubovima Sunčevog sistema, interstelarna putovanja su omogudena. Kada je na Zemlji bila godina 5102., ljudska rasa je napravila robote RII koji su dobili zadatak da brane određene zvijezde i planete koje kruže oko njih. Interstelarne ambasade su se dogovorile da zbog sve vedeg broja stelarnih parazita počnu iz Sunčevog sistema slati po jednog robota do svake od pogođenih zvijezda (uključujudi i samo Sunce), kako bi paraziti bili uništeni. Roboti de putovati od Sunčevog sistema da dođu do tih zvijezda, tako da de svaki od njih biti zadužen za odbranu tačno jedne od njih. Kako bi se uštedilo na projektu, vama je dat zadatak da pronađete najmanju jačinu radio opreme koja se mora ugraditi u svakog robota, tako da svaka dva robota mogu međusobno komunicirati. Smatra se da roboti mogu međusobno komunicirati ako im je međusobna udaljenost preko interstelarnih puteva manja ili jednaka jačini radio opreme ugrađene u njih. Odnosno, da bi roboti koji se nalaze na udaljenosti od 5000 mogli komunicirati, moraju imati ugrađenu opremu jačine minimalno 5000. Svim robotima se ugrađuje ista radio oprema. Na vašu sredu, zadatak je olakšan činjenicom da su interstelarni putevi vrlo, vrlo skupi, tako da između svake dvije zvijezde postoji tačno jedan put (direktni ili indirektni preko drugih zvijezda), što znači da ukoliko imamo N zvijezda, onda demo imati tačno N - 1 interstelarnih puteva među nekima od njih. Putevi de biti opisani preko početne i krajnje zvijezde, te dužine tog puta između njih. Svi putevi su dvosmjerni.
Zadatak
Vaš zadatak je da napravite program koji implementira sljededu funkciju:
int Rasporedi(int N, int A[ ], int B[ ], int C[ ]);
Gdje je N broj zvijezda pod utjecajem parazita. Nizovi A, B i C imaju po tačno N - 1 elemenata i definirani su tako da za neki indeks i < N znači da su zvijezde A[i] i B[i] (svi indeksi su između 1 i N, uključujudi, pri čemu je indeks 1 uvijek Sunčev sistem) povezane putem dužine C[i] (naravno, put je dvosmjeran i čitava mreža puteva zadovoljava uslove opisane u zadatku). Povratna vrijednost ove funkcije je minimalna vrijednost jačine radio opreme koja se mora ugraditi u svakog robota prije polaska iz Sunčevog sistema.
Primjer
Rasporedi(4, {1, 2, 2}, {2, 3, 4}, {5, 8, 2}) = 13
Bodovanje i ograničenja
Zadatak de biti testiran na četiri podzadatka, od kojih svaki nosi određeni broj bodova i ima sljededa ograničenja:
Podzadatak 1 (5 bodova): N <= 10
Podzadatak 2 (10 bodova): N <= 1000
Podzadatak 3 (26 bodova): N <= 10000
Podzadatak 4 (59 bodova): N <= 100000
Uvijek vrijedi: 1 <= A[i], B[i] <= N i 1 <= C[i] <= 100
Vremenska i memorijska ograničenja su dostupna na sistemu za ocjenjivanje.

ovo je rijesenje ali nisam siguran posto sam blejio u to ko tele u sarena vrata

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

vector<vector<pair<int,int> > > ve;
int maxiD,maxiC;
void dfs(int x,int p,int d)
{
if(d>maxiD)
{
maxiD=d;maxiC=x;
}
for(int i=0;i<ve[x].size();i++)
{
if(ve[x][i].first!=p)
dfs(ve[x][i].first,x,d+ve[x][i].second);
}
}

int Rasporedi(int N,int A[],int B[],int C[])
{
ve.clear();ve.resize(N);
for(int i=0;i<N-1;i++)
{
ve[A[i]-1].push_back(make_pair(B[i]-1,C[i]));
ve[B[i]-1].push_back(make_pair(A[i]-1,C[i]));
}
/*
for(int i=0;i<n;i++)
dfs(i,-1,0);//brute force!
return maxiD;*/
maxiC=0;maxiD=0;
dfs(0,-1,0);
int l=maxiC;
maxiC=0;maxiD=0;
dfs(l,-1,0);
return maxiD;
}