fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. struct custom_hash
  6. {
  7.     static uint64_t splitMix64(uint64_t x)
  8.     {
  9.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  10.         x += 0x9e3779b97f4a7c15;
  11.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  12.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  13.         return x ^ (x >> 31);
  14.     }
  15.     template<typename T1, typename T2>
  16.     size_t operator()(const pair<T1,T2>& x) const
  17.     {
  18.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  19.         return splitMix64(x.first + FIXED_RANDOM) ^ (splitMix64(x.second + FIXED_RANDOM) << 1);
  20.     }
  21. };
  22.  
  23. struct Node
  24. {
  25.     ll Value;
  26.     Node *LeftChild, *RightChild; // Pointers to left child and right child
  27.  
  28.     Node(const ll &val = 0)
  29.     {
  30.         Value = val;
  31.         LeftChild = nullptr;
  32.         RightChild = nullptr;
  33.     }
  34.     ~Node() // Destructor. Notice the "~" character before the struct name.
  35.     {
  36.         delete LeftChild;
  37.         delete RightChild;
  38.         LeftChild = nullptr;
  39.         RightChild = nullptr;
  40.     }
  41. };
  42.  
  43. int M;
  44. unordered_map<pair<int,ll>, int, custom_hash> subtreeMap; // {hash -> {size, sum}}
  45. bool check = false;
  46.  
  47. pair<int, ll> dfs(Node *root)
  48. {
  49.     if (root == nullptr)
  50.         return {0, 0};
  51.  
  52.     const auto &left = dfs(root->LeftChild);
  53.     const auto &right = dfs(root->RightChild);
  54.  
  55.     int size = 1 + left.first + right.first;
  56.     ll sum = root->Value + left.second + right.second;
  57.  
  58.     if (size > M)
  59.     {
  60.         if (subtreeMap.count({size, sum}))
  61.             check = true;
  62.         else
  63.             subtreeMap[{size, sum}]++;
  64.     }
  65.     return {size, sum};
  66. }
  67.  
  68. int main()
  69. {
  70.     ios_base::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.     int N;
  73.     cin >> N >> M;
  74.     vector<int> nodes(N);
  75.     for (int i = 0; i < N; i++)
  76.         cin >> nodes[i];
  77.  
  78.     vector<Node *> tree;
  79.     for (int i = 0; i < N; i++)
  80.         tree.push_back(new Node(nodes[i]));
  81.  
  82.     int E;
  83.     cin >> E;
  84.     for (int i = 0; i < E; i++)
  85.     {
  86.         char dir;
  87.         int parentIdx, childIdx;
  88.         cin >> dir >> parentIdx >> childIdx;
  89.         if (dir == 'L')
  90.             tree[parentIdx]->LeftChild = tree[childIdx];
  91.         else
  92.             tree[parentIdx]->RightChild = tree[childIdx];
  93.     }
  94.  
  95.     Node *root = tree[0]; // Root node
  96.     dfs(root);
  97.     cout << check;
  98.     return 0;
  99. }
Success #stdin #stdout #stderr 0.26s 40660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/TiEvAK
language:
R (R 3.5.2)
created:
5 days 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!