Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 29 ]  Przejdź na stronę Poprzednia strona  1, 2, 3
Górnicy - testy 
Autor Wiadomość
Gwiazda 2

Dołączył(a): 31 maja 2010, o 11:31
Posty: 20
Post Re: Górnicy - testy
Anisiak napisał(a):
Damian Trojnar napisał(a):
Podzieli sie ktoś rozwiązaniem tego zadania? Bo ja mam dobrze, ale TLE. Chcialbym zobaczyć wzorcowe rozwianie.


Ja zrobiłam to tak:
obliczyłam bfs-em dla każdej komory jakiej maksymalnej wysokości może się do niej dostać pracownik i zapisuje, dane do tablicy;

ponieważ wysokości ludzi i *komór są z przedziału od 1 do 1000 zastosowałam sortowanie kubełkowe;

a potem zachłannie przydzielałam najwyższych pracowników do najwyższych komór.

mam nadzieje, że trochę rozjaśniłam;

*chodzi o wysokości tuneli, aby dostać się do danej komory.

pozdrawiam
Anisiak


Ja robie podobnie oprocz tego BFS'a
np dla. takiego testu:
1
4 4
2 1 1
3 1 2
1 4 3
3
1 1 1
Robie tak:
poziom 0 - indeksy: 4
zwieksz ilosc poziomow
lece po wszystkich tunelach i dodaje do ostatniego poziomu jesli a jest rowne ktoremus z indeksow na poziomie 0 to do poziomu 1 dodaje b (przy okazji maxwys dla komory[b] = min( komora[a].maxwys, aktualnytunel.maxwys); ) po czym usuwam dany tunel. Jeśli b jest rowne ktoremus z indeksow na poziomie 0 to tak samo tylko na odwrot :D
poziom 1- indeksy : 1
zwieksz ilosc poziomow
i znowu lece po tunelach...
poziom 2 - indeksy: 2 oraz 3
koniec bo ilosc dodanych tuneli jest rowna n-1 :D
To chyba daje O((E / 2) * V); co jak wiadomo jest o wiele za duzo :D

Weż się ktoś podziel kodem to sobie przeanalizuje tego BFS'a, bo nigdy wczesniej nie robilem zadan z grafow i sam sobie nie poradze :cry:


31 paź 2010, o 11:25
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 31 maja 2009, o 18:24
Posty: 107
Post Re: Górnicy - testy
http://wklej.org/hash/8396113cdcc/
Proszę bardzo ;).


31 paź 2010, o 11:31
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 10:02
Posty: 83
Post Re: Górnicy - testy
Aleksander Łukasiewicz napisał(a):
http://wklej.org/hash/8396113cdcc/
Proszę bardzo ;).

Bez sortowania kubełkowego masz?;)
a jakie masz czasy:P

Test Wynik Czas Pamięć
0.out accepted 0.00s 2220
1.out accepted 0.00s 2220
2.out accepted 0.00s 2220
3.out accepted 0.00s 2220
4.out accepted 0.00s 2352
5.out accepted 0.00s 2220
6.out accepted 0.04s 3332
7.out accepted 0.13s 5572
8.out accepted 0.12s 5408
9.out accepted 0.57s 15608
10.out accepted 0.68s 20756


31 paź 2010, o 11:39
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 31 maja 2009, o 18:24
Posty: 107
Post Re: Górnicy - testy
Jeśli dobrze pamiętam, to to co zastosowałem nazywa się sortowaniem przez zliczanie.
Kod:
Test    Wynik   Czas    Pamięć
0.out   accepted    0.00s   1828
1.out   accepted    0.00s   1828
2.out   accepted    0.00s   1828
3.out   accepted    0.00s   1828
4.out   accepted    0.00s   1828
5.out   accepted    0.00s   1828
6.out   accepted    0.04s   2532
7.out   accepted    0.11s   3940
8.out   accepted    0.11s   3808
9.out   accepted    0.48s   10672
10.out  accepted    0.64s   14304


31 paź 2010, o 11:49
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 27 paź 2009, o 00:30
Posty: 138
Post Re: Górnicy - testy
Aleksander Łukasiewicz napisał(a):
Jeśli dobrze pamiętam, to to co zastosowałem nazywa się sortowaniem przez zliczanie.


Zależy od źródła. "Wprowadzenie do algorytmów" wprowadza dużo zamieszania nazywając sortowaniem kubełkowym taki w zasadzie nieprzydatny algorytm.
Ale poza "Wprowadzeniem" sortowanie przez zliczanie = sortowanie kubełkowe

_________________
Mięso = Morderstwo


31 paź 2010, o 11:52
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 23 lis 2009, o 23:00
Posty: 101
Post Re: Górnicy - testy
Kod:

//SKI 2010
//Zadanie: Górnicy
//Autor: Łukasz Wałejko
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> leafs;
vector<vector<pair<int,int> > > graph;
int k;
void dfs(int v,int p,int h)
{
  if(graph[v].size()==1&&v!=k)
  {
    leafs.push_back(h);
  }
  for(int i=0;i<graph[v].size();++i)
  {
    if(graph[v][i].first==p)continue;
    dfs(graph[v][i].first,v,min(h,graph[v][i].second));
  }
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    leafs.clear();
    graph.clear();
    int n;
    scanf("%d%d",&n,&k);
    int a,b,c;
    graph.resize(n+1);
    for(int i=0;i<n-1;++i)
    {
      scanf("%d%d%d",&a,&b,&c);
      graph[a].push_back(pair<int,int>(b,c));
      graph[b].push_back(pair<int,int>(a,c));
    }
    dfs(k,-1,1000000001);
    sort(leafs.begin(),leafs.end());
    int m;
    scanf("%d",&m);
    vector<int> miners;
    miners.resize(m);
    for(int i=0;i<m;++i)
    {
      scanf("%d",&miners[i]);
    }
    sort(miners.begin(),miners.end());
    int x=0;
    for(int i=0,j=0;i<leafs.size()&&j<miners.size();++i)
    {
      if(miners[j]<=leafs[i])
      {
        ++x;
        ++j;
      }
    }
    printf("%d\n",x);
  }
  return 0;
}
 

:P


31 paź 2010, o 12:03
Zobacz profil
Gwiazda 2

Dołączył(a): 31 maja 2010, o 11:31
Posty: 20
Post Re: Górnicy - testy
Wielkie dzięki. BTW jakie książki o algorytmach i strukturach danych polecacie w sensie pod konkursy ^^ :?:


31 paź 2010, o 14:45
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 25 paź 2009, o 12:35
Posty: 37
Post Re: Górnicy - testy
Łukasz Wałejko napisał(a):
Kod:

vector<int> leafs;
 

:P

Jak już chcesz być tró i pisać po angielsku, to liście są leaves :P


31 paź 2010, o 15:43
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 23 lis 2009, o 23:00
Posty: 101
Post Re: Górnicy - testy
Jakub Sygnowski napisał(a):
Łukasz Wałejko napisał(a):
Kod:

vector<int> leafs;
 

:P

Jak już chcesz być tró i pisać po angielsku, to liście są leaves :P

Yup, masz rację, aż sprawdziłem :P Aczkolwiek wymowa IMHO podobna...


31 paź 2010, o 19:30
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 29 ]  Przejdź na stronę Poprzednia strona  1, 2, 3


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 3 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL