daily pastebin goal
25%
SHARE
TWEET

Untitled

a guest Apr 17th, 2017 197 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include "testlib.h"
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 2010;
  7.  
  8. int n;
  9. int orig_tree[MAXN];
  10. string orig_hash;
  11. vector<int> child[MAXN];
  12. bool vis[MAXN];
  13. bool hascycle;
  14.  
  15.  
  16. string dfs(int root) {
  17.     if (vis[root]) {
  18.         hascycle = true;
  19.         return "";
  20.     }
  21.     vis[root] = true;
  22.     if (child[root].size() == 0) {
  23.         return "()";
  24.     }
  25.  
  26.     string a[2];
  27.     int aidx = 0;
  28.     for (auto x : child[root]) {
  29.         a[aidx++] = dfs(x);
  30.     }
  31.     if (a[0] > a[1]) {
  32.         return "(" + a[1] + a[0] + ")";
  33.     } else {
  34.         return "(" + a[0] + a[1] + ")";
  35.     }
  36. }
  37.  
  38. string getHash(int tree[]) {
  39.     hascycle = false;
  40.     for (int i = 1; i <= 2 * n - 1; i++) {
  41.         child[i].clear();
  42.         vis[i] = false;
  43.     }
  44.     int root = -1;
  45.     for (int i = 1; i <= 2 * n - 1; i++) {
  46.         if (tree[i] == -1) {
  47.             root = i;
  48.         } else {
  49.             child[tree[i]].push_back(i);
  50.         }
  51.     }
  52.  
  53.     return dfs(root);
  54. }
  55.  
  56. inline int readAns(InStream& in) {
  57.     int qs = in.readInt();
  58.     if (qs > 10 * n) {
  59.         in.quitf(_wa, "Too many questions %d", qs);
  60.     }
  61.     int tree[MAXN];
  62.     int used[MAXN];
  63.     for (int i = 0; i <= 2 * n - 1; i++) used[i] = 0;
  64.     int root = -1;
  65.     for (int i = 1; i <= 2 * n - 1; i++) {
  66.         tree[i] = in.readInt(-1, 2*n-1);
  67.         if (tree[i] == 0) {
  68.             in.quitf(_wa, "label of parent should be between 1 and 2*n-1");
  69.         }
  70.         if (tree[i] == -1) {
  71.             if (root != -1) {
  72.                 in.quitf(_wa, "Found multiple roots %d %d", i, root);
  73.             }
  74.             root = i;
  75.         } else {
  76.             used[tree[i]]++;
  77.         }
  78.     }
  79.     if (root == -1) {
  80.         in.quitf(_wa, "Didn't find a root");
  81.     }
  82.     for (int i = 1; i <= 2 * n - 1; i++) {
  83.         if (used[i] != 0 && used[i] != 2) {
  84.             in.quitf(_wa, "Each node must have exactly 0 or 2 children %d %d", i, used[i]);
  85.         }
  86.     }
  87.  
  88.     string c_hash = getHash(tree);
  89.     if (hascycle) {
  90.         in.quitf(_wa, "Output has cycles");
  91.     }
  92.  
  93.     for (int i = 1; i <= 2 * n - 1; i++) {
  94.         if (!vis[i]) {
  95.             in.quitf(_wa, "Not all nodes reachable from root.");
  96.         }
  97.     }
  98.  
  99.     if (orig_hash != c_hash) {
  100.         in.quitf(_wa, "Trees are not isomorphic");
  101.     }
  102.    
  103.     return qs;
  104. }
  105.  
  106. int main(int argc, char* argv[]) {
  107.     registerTestlibCmd(argc, argv);
  108.  
  109.     n = inf.readInt();
  110.     for (int i = 1; i <= 2 * n - 1; i++) {
  111.         orig_tree[i] = inf.readInt();
  112.     }
  113.     orig_hash = getHash(orig_tree);
  114.  
  115.     int a = readAns(ans);
  116.     int b = readAns(ouf);
  117.  
  118.     quitf(_ok, "Found tree in %d questions!", b);
  119. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top