Cześć, mam problem z zadaniem http://main.edu.pl/pl/archive/oi/20/luk. Mój kod dostaje 30 pkt, reszta to WA, pomysł wygląda następująco: znajduję w drzewie najbardziej pesymistyczną ścieżkę (czyli poddrzewami w których jest najwięcej wierzchołków) i robię binsearcha po wyniku symulując przejście króla ową ścieżką. Dodam swój kod, może to nieco pomoże (tak wiem, że trochę bałagan się zrobił wyprzedzając komentarze). Prosze o pomoc, podzielenie się swoim pomysłem na rozwiązanie etc.
Pozdrawiam
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define range 300001
vector < vector <int> > G;
vector < vector <int> > depth;
vector <int> path;
int direction[range], ilosc_dzieci[range], lvl[range];
bool visited[range];
int n, ostatni_poziom=0, max_tmp, kolejny_wierzcholek;
queue <int> Q;
int bfs(int capital)
{
Q.push(capital);
visited[capital]=true;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
int l = 0;
for(int i=0; i<G[u].size(); i++)
{
int v = G[u][i];
if(visited[v]==false)
{
Q.push(v);
visited[v] = true;
direction[v] = u;
lvl[v] = lvl[u]+1;
depth[lvl[v]].push_back(v);
if(lvl[v] > ostatni_poziom)
ostatni_poziom = lvl[v];
}
}
}
}
int dfs(int v)
{
visited[v]=0; // zaznaczam ze odwiedzony
max_tmp = 0;
for(int i=0; i<G[v].size(); i++)
{
int u = G[v][i];
if(ilosc_dzieci[u] > max_tmp && visited[u]==1)
{
max_tmp = ilosc_dzieci[u];
kolejny_wierzcholek = u;
}
}
if(visited[kolejny_wierzcholek]==1)
{
path.push_back(kolejny_wierzcholek);
dfs(kolejny_wierzcholek);
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n, a, b;
cin >> n;
if(n==1)
{
cout << 0;
return 0;
}
G.resize(n+1);
depth.resize(n+1);
for(int i=0; i<n-1; i++)
{
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
bfs(1);
for(int i=ostatni_poziom; i>=1; i--)
{
for(int j=0; j<depth[i].size(); j++)
{
int v = depth[i][j];
ilosc_dzieci[direction[v]]++;
ilosc_dzieci[direction[v]]+=ilosc_dzieci[v];
}
}
// wyznaczam sciezke pesymistyczna
path.push_back(1);
dfs(1);
vector<int> finish;
finish.push_back(G[1].size());
for(int i=1; i<path.size(); i++)
finish.push_back(G[path[i]].size()-1);
int pocz=1, kon=range, out=range;
for(int i=0; i<path.size(); i++)
cout << path[i] << " ";
cout << endl;
for(int i=0; i<finish.size(); i++)
cout << finish[i] << " ";
cout << endl;
while(pocz!=kon)
{
int robotnicy=(pocz+kon)/2;
int ile_razy=0, suma=0, tmp, f=0, ilosc_krokow=0;
for(int i=0; i<finish.size(); i++)
{
tmp = finish[i];
if(suma-tmp<0)
{
while(suma-tmp<0)
{
suma+=robotnicy;
ile_razy++;
}
//cout << suma << " * " << ile_razy << endl;
}
suma-=tmp;
ilosc_krokow++;
if(ilosc_krokow < ile_razy)
{
f=1;
break;
}
}
cout << endl << robotnicy << " " << ilosc_krokow<< " " << ile_razy << " " << f << endl;
if(ile_razy <= ilosc_krokow && f==0)
{
out=min(out, robotnicy);
if(robotnicy==pocz || robotnicy==kon)
break;
kon=robotnicy;
}
else
{
if(robotnicy==pocz || robotnicy==kon)
break;
pocz=robotnicy;
}
}
cout << out;
}
