Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- typedef unsigned long int ulint;
- struct kraj{
- int p;
- ulint w;
- };
- int main(){
- ios_base::sync_with_stdio(false);
- int n,i,k,p,max;
- ulint m,j,w,ile=0;
- kraj *K; //tablica - kopiec
- cin>>n;
- int panstwa[1001];
- K = new kraj[n];
- // kraj kr;
- int pom, pom2;
- for(i=0;i<n;i++)
- {
- cin >> p >> w;
- //cin>>K[i].p >> K[i].w;
- K[i].p = p;
- K[i].w = w;
- panstwa[p]=i;
- }
- cin>>m;
- for(j=0;j<m;j++)
- {
- cin>>p>>w;
- // i=0;
- i = panstwa[p];
- // while(K[i].p != p) //znajduje indeks odpowiedniego panstwa..
- // i++;
- K[i].w = w; //.. i nadaje mu nowy wspolczynnik
- //TAB[SZUKANY] 'k'=OJCIEC
- if((i>0)&&(w > K[k = (i-1)/2].w))
- { //jezeli K[i] jest wiekszy od ojca (o ile MA ojca)
- while((i>0)&&(w>K[k].w))
- { //przesuwa K[i] w gore odpowiednia ilosc razy
- //k=(i-1)/2; // indeks ojca
- //zamienia miejscami K[i] z K[k]:
- //tab[ojciec].wsp pom=K[k].p;
- //tab[szukany].wsp pom2=K[i].p;
- swap(panstwa[pom2],panstwa[pom] );
- swap(K[i],K[k]);
- ile++;
- i = k; k = (i-1)/2;
- }
- }
- else
- {
- k=2*i+1;
- if(((k<n)&&(w<K[k].w)) || ((k+1<n)&&(w<K[k+1].w)))
- { //.. a jezeli K[i] MA lewego/prawego syna - i jest od ktoregos mniejszy..
- /*k=lsyn*/ while(((k<n)&&(w<K[k].w)) || ((k+1<n)&&(w<K[k+1].w)))
- { //przesuwa K[i] w dol
- if((k+1<n)&&(K[k+1].w>K[k].w)) //okresla wiekszego z synow
- max = k+1; //prawy jest wiekszy
- else
- max = k; //lewy jest wiekszy //max to index wiekszego z synow elementu K[i]
- //zamienia miejscami K[i] z K[max]:
- pom=K[max].p;
- pom2=K[i].p;
- swap(panstwa[pom2],panstwa[pom] );
- swap(K[i],K[max]);
- ile++;
- i=max; k=2*i+1;
- }
- }
- }
- }
- cout<<ile;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement