Advertisement
Guest User

Untitled

a guest
Nov 19th, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include <utility>
  2. #include <vector>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <set>
  6. #include <sstream>
  7. #include <list>
  8.  
  9. using namespace std;
  10.  
  11. class DS {
  12. public:
  13.     DS(int n) : parentOfEach(n), countOfEach(n), minOfEach(n), maxOfEach(n) {
  14.         for (int i = 0; i != n; i++) {
  15.             parentOfEach[i] = i;
  16.             countOfEach[i] = 1;
  17.             minOfEach[i] = i;
  18.             maxOfEach[i] = i;
  19.         }
  20.     }
  21.  
  22.     vector<int> parentOfEach;
  23.     vector<int> countOfEach;
  24.     vector<int> minOfEach;
  25.     vector<int> maxOfEach;
  26.  
  27.     int GetCount(int index) {
  28.         return countOfEach[GetElement(index)];
  29.     }
  30.  
  31.     int GetMax(int index) {
  32.         return maxOfEach[GetElement(index)];
  33.     }
  34.  
  35.     int GetMin(int index) {
  36.         return minOfEach[GetElement(index)];
  37.     }
  38.  
  39.     void Union(int lhs, int rhs) {
  40.         if (!Check(lhs, rhs)) {
  41.             countOfEach[GetElement(lhs)] += countOfEach[GetElement(rhs)];
  42.             if (minOfEach[GetElement(lhs)] < minOfEach[GetElement(rhs)])
  43.                 minOfEach[GetElement(lhs)] = minOfEach[GetElement(rhs)];
  44.             if (maxOfEach[GetElement(lhs)] > maxOfEach[GetElement(rhs)])
  45.                 maxOfEach[GetElement(lhs)] = maxOfEach[GetElement(rhs)];
  46.             parentOfEach[GetElement(rhs)] = GetElement(lhs);
  47.         }
  48.     }
  49.  
  50.     int GetElement(int index) {
  51.         return parentOfEach[index] == index
  52.                ? index
  53.                : parentOfEach[index] = GetElement(parentOfEach[index]);
  54.     }
  55.  
  56.     bool Check(int lhs, int rhs) {
  57.         return GetElement(lhs) == GetElement(rhs);
  58.     }
  59. };
  60.  
  61. int main() {
  62.     ifstream reader("dsu.in");
  63.     ofstream writer("dsu.out");
  64.     int n;
  65.     reader >> n;
  66.     DS u(n);
  67.     string s;
  68.     while (true) {
  69.         string command;
  70.         if (reader.eof())
  71.             break;
  72.         reader >> command;
  73.         if (command == "union") {
  74.             int a, b;
  75.             reader >> a >> b;
  76.             u.Union(a - 1, b - 1);
  77.         } else if (command == "get") {
  78.             int a;
  79.             reader >> a;
  80.             int cnt = u.GetCount(a - 1);
  81.             int mx = u.GetMax(a - 1) + 1;
  82.             int mn = u.GetMin(a - 1) + 1;
  83.             writer << mx << " " << mn << " " << cnt << "\n";
  84.         }
  85.     }
  86.     writer.close();
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement