Wrocławski Portal Informatyczny
http://informatyka.wroc.pl/forum/

Górnicy - testy
http://informatyka.wroc.pl/forum/viewtopic.php?f=70&t=770
Strona 3 z 3

Autor:  Damian Trojnar [ 31 paź 2010, o 11:25 ]
Tytuł:  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:

Autor:  Aleksander Łukasiewicz [ 31 paź 2010, o 11:31 ]
Tytuł:  Re: Górnicy - testy

http://wklej.org/hash/8396113cdcc/
Proszę bardzo ;).

Autor:  Anita Wróblewska [ 31 paź 2010, o 11:39 ]
Tytuł:  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

Autor:  Aleksander Łukasiewicz [ 31 paź 2010, o 11:49 ]
Tytuł:  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

Autor:  Jan Kanty Milczek [ 31 paź 2010, o 11:52 ]
Tytuł:  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

Autor:  Łukasz Wałejko [ 31 paź 2010, o 12:03 ]
Tytuł:  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

Autor:  Damian Trojnar [ 31 paź 2010, o 14:45 ]
Tytuł:  Re: Górnicy - testy

Wielkie dzięki. BTW jakie książki o algorytmach i strukturach danych polecacie w sensie pod konkursy ^^ :?:

Autor:  Jakub Sygnowski [ 31 paź 2010, o 15:43 ]
Tytuł:  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

Autor:  Łukasz Wałejko [ 31 paź 2010, o 19:30 ]
Tytuł:  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...

Strona 3 z 3 Strefa czasowa: UTC + 1 [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/