fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. using namespace std;
  6.  
  7. int iloscPracownikow;
  8. int bezposredniPrzlozony[1000002];
  9. int pensja[1000002];
  10. vector < vector <int> > spisPrzelozonych;
  11. int iloscPodwladnych[1000002];
  12. int pozycjaSzefa;
  13. bool niejedno[1000002];
  14. int podDrzewa[1000002];
  15. vector <int> p;
  16. vector <int> k;
  17. int pStop;
  18. int kStop;
  19. vector <int> listaK;
  20.  
  21. int zliczPodwladnych(int a){
  22. 	int podwladni = spisPrzelozonych.at(a).size();
  23. 	for (int i=0;i<spisPrzelozonych.at(a).size();i++){
  24. 		podwladni=podwladni+zliczPodwladnych(spisPrzelozonych.at(a).at(i));
  25. 	}
  26. 	iloscPodwladnych[a]=podwladni;
  27. 	return podwladni;
  28.  
  29. }
  30.  
  31. void przypisz(int pracownik){
  32. 	if(niejedno[listaK.at(listaK.size()-1)]==false){
  33. 		pensja[pracownik]=listaK.back();
  34. 		listaK.pop_back();
  35. 	}
  36. 	if(spisPrzelozonych.at(pracownik).size()==1)
  37. 		przypisz(spisPrzelozonych.at(pracownik).at(0));
  38. }
  39.  
  40. int main() {
  41.  
  42. 	cin >> iloscPracownikow;
  43. 	spisPrzelozonych.resize(1000002);
  44. 	pStop=0;
  45. 	kStop=0;
  46. 	for(int i=1;i<=iloscPracownikow;i++){
  47. 		int przelozony;
  48. 		int pen;
  49. 		cin >> przelozony;
  50. 		cin >> pen;
  51. 		if(przelozony==i){
  52. 			pensja[i]=iloscPracownikow;
  53. 			pozycjaSzefa=i;
  54. 		}
  55. 		else{
  56. 			bezposredniPrzlozony[i]=przelozony;
  57. 			spisPrzelozonych.at(przelozony).push_back(i);
  58. 			pensja[i]=pen;
  59. 		}
  60.  
  61.  
  62.  
  63.  
  64. 	}
  65. 	/*for(int i=1;i<=iloscPracownikow;i++)
  66. 		cout<<bezposredniPrzlozony[i]<<" "<<pensja[i]<<" "<<endl;*/
  67. 	zliczPodwladnych(pozycjaSzefa);
  68.  
  69. 	/*for(int i=1;i<=iloscPracownikow;i++)
  70. 		cout<<iloscPodwladnych[i]<<endl;
  71. 	cout<<endl;*/
  72.  
  73. 	for(int i=1;i<=iloscPracownikow;i++){
  74.  
  75. 			niejedno[i]=false;
  76.  
  77.  
  78. 	}
  79.  
  80. 	for(int i=1;i<=iloscPracownikow;i++){
  81. 		if(pensja[i]==0 && pensja[bezposredniPrzlozony[i]]!=0)
  82. 			podDrzewa[pensja[bezposredniPrzlozony[i]]]=i;
  83.  
  84.  
  85.  
  86. 	}
  87.  
  88. 	/*for(int i=1;i<=iloscPracownikow;i++)
  89. 		cout<<podDrzewa[i]<<endl;
  90. 	cout<<endl;*/
  91.  
  92. 	for(int i=1;i<=iloscPracownikow;i++){
  93. 		if (pensja[i]==0){
  94. 		k.push_back(i);
  95. 		p.push_back(i);
  96. 		}
  97. 	}
  98.  
  99. 	for(int i=0;i<=k.size();i++)
  100. 		cout<<p.at(i)<<" "<<k.at(i)<<endl;
  101. 	cout<<endl;
  102.  
  103. 	for(int i=0;i<iloscPracownikow;i++){
  104.  
  105. 		if(podDrzewa[i]==0){
  106. 			for(int x=0;x<spisPrzelozonych.at(podDrzewa[i]).size();x++){
  107. 				if(pensja[podDrzewa[i]]==0){
  108. 					listaK.clear();
  109. 					for(int a=0;a<iloscPodwladnych[podDrzewa[i]];a++){
  110. 						listaK.push_back(k.at(0));
  111. 						k.erase(p.begin());
  112. 					}
  113. 					if(k.size()==0||k.at(0)>i){
  114. 						if(niejedno[listaK.at(listaK.size()-1)]==false){
  115. 							przypisz(podDrzewa[i]);
  116. 						}
  117.  
  118. 					}
  119. 					else{
  120. 						while(p.size()!=0&&p.at(0)<i){
  121. 							niejedno[p.at(0)]=true;
  122. 							p.erase(p.begin());
  123. 						}
  124.  
  125. 					}
  126. 				}
  127. 			}
  128. 		}	
  129.  
  130. 	}
  131.  
  132. 	for(int i=1;i<=iloscPracownikow;i++)
  133. 		cout<<pensja[i]<<endl;
  134. }
  135.  
  136.  
Runtime error #stdin #stdout #stderr 0s 56112KB
comments (?)
stdin
copy 
10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0
stdout
copy 
3 3
6 6
7 7
8 8
9 9
10 10
stderr
copy 
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 6) >= this->size() (which is 6)
https://ideone.com/asHb4J
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!