Guest User

Untitled

a guest
May 19th, 2016
310
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. map<pair<int,int>,int> cod;
  5. int idx;
  6. set<int> ret;
  7. int t[1<<21];
  8. class Tree
  9. {
  10.     public:
  11.     Tree() { memset(t,-1,sizeof(t)); }
  12.     void insert(int k)
  13.     {
  14.         int node = 1;
  15.         while (t[node] != -1)
  16.         {
  17.             int p = (t[node]<k);
  18.             node = 2*node+p;
  19.         }
  20.         t[node] = k;
  21.     }
  22.     int code(int node)
  23.     {
  24.         if (t[node] == -1) return -1;
  25.         if (t[2*node] == -1 && t[2*node+1] == -1) return 0;
  26.         if (cod[make_pair(code(2*node),code(2*node+1))])
  27.             return cod[make_pair(code(2*node),code(2*node+1))];
  28.         return cod[make_pair(code(2*node),code(2*node+1))] = idx++;
  29.     }
  30. };
  31.  
  32. int main()
  33. {
  34.     int N,K; cin >> N >> K;
  35.     idx = 1;
  36.     for (int i = 0; i < N; i++)
  37.     {
  38.         Tree t;
  39.         for (int j = 0; j < K; j++)
  40.         {
  41.             int X; cin >> X;
  42.             t.insert(X);
  43.         }
  44.         ret.insert(t.code(1));
  45.     }
  46.     cout << ret.size() << endl;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment