fork download
copy 
  1. //
  2. // Created by Bhagirathi on 2019-04-21.
  3. //
  4.  
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <sstream>
  10. #include <queue>
  11. #include <deque>
  12. #include <bitset>
  13. #include <iterator>
  14. #include <list>
  15. #include <stack>
  16. #include <map>
  17. #include <set>
  18. #include <functional>
  19. #include <numeric>
  20. #include <utility>
  21. #include <limits>
  22. #include <time.h>
  23. #include <math.h>
  24. #include <stdio.h>
  25. #include <string.h>
  26. #include <stdlib.h>
  27. #include <assert.h>
  28. #include <algorithm>
  29. #include <chrono>
  30. #include <random>
  31. #include <vector>
  32. using namespace std;
  33.  
  34. /*******  All Required define Pre-Processors and typedef Constants *******/
  35. #define SCD(t) scanf("%d",&t)
  36. #define SCLD(t) scanf("%ld",&t)
  37. #define SCLLD(t) scanf("%lld",&t)
  38. #define SCC(t) scanf("%c",&t)
  39. #define SCS(t) scanf("%s",t)
  40. #define SCF(t) scanf("%f",&t)
  41. #define SCLF(t) scanf("%lf",&t)
  42. #define MEM(a, b) memset(a, (b), sizeof(a))
  43. #define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
  44. #define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
  45. #define REP(i, j) FOR(i, 0, j, 1)
  46. #define RREP(i, j) RFOR(i, j, 0, 1)
  47. #define all(cont) cont.begin(), cont.end()
  48. #define rall(cont) cont.end(), cont.begin()
  49. #define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
  50. #define IN(A, B, C) assert( B <= A && A <= C)
  51. #define MP make_pair
  52. #define PB push_back
  53. #define INF (int)1e9
  54. #define EPS 1e-9
  55. #define PI 3.1415926535897932384626433832795
  56. #define MOD 1000000007
  57. #define read(type) readInt<type>()
  58. const double pi=acos(-1.0);
  59. typedef pair<int, int> PII;
  60. typedef vector<int> VI;
  61. typedef vector<string> VS;
  62. typedef vector<PII> VII;
  63. typedef vector<VI> VVI;
  64. typedef map<int,int> MPII;
  65. typedef set<int> SETI;
  66. typedef multiset<int> MSETI;
  67. typedef long int int32;
  68. typedef unsigned long int uint32;
  69. typedef long long int int64;
  70. typedef unsigned long long int  uint64;
  71.  
  72. mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
  73.  
  74. /****** Template of some basic operations *****/
  75. template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
  76. template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
  77. /**********************************************/
  78.  
  79. using namespace std;
  80.  
  81. const int MAXN = (int)1e7;
  82. const int LOGMAXN = 31;
  83.  
  84. int zero[MAXN],one[MAXN],leafValue[MAXN];
  85. int nodeCount = 0;
  86. int root[MAXN],currRoot=0;
  87. map<int64,int> idToNodeNumber;
  88. map<int64,int> idToEncryption;
  89. map<int64,VI> adj;
  90.  
  91. int64 maxAns=0,minAns=0;
  92.  
  93. void printDFS(int i, int64 r);
  94.  
  95. int newNode(int lef, int rig) {
  96.     int p = ++nodeCount;
  97.     zero[p] = lef;
  98.     one[p] = rig;
  99.     return p;
  100. }
  101.  
  102. int newLeaf(int val) {
  103.     int p = ++nodeCount;
  104.     zero[p]=one[p]=0;
  105.     leafValue[p] = val;
  106.     return p;
  107. }
  108.  
  109. int countBits(int n)
  110. {
  111.     int count = 0;
  112.     while (n)
  113.     {
  114.         count++;
  115.         n >>= 1;
  116.     }
  117.     return count;
  118. }
  119.  
  120. void maxXOR(int trieIndex,int val,int valBitIndex,int appendZeroes){
  121.  
  122.     if(appendZeroes>0){
  123.         if(one[trieIndex]!=0){ //want to go right
  124.             maxXOR(one[trieIndex],val,valBitIndex,appendZeroes-1);
  125.             maxAns += (int)pow(2,valBitIndex+appendZeroes-1);
  126.         }
  127.         else{
  128.             maxXOR(zero[trieIndex],val,valBitIndex,appendZeroes-1);
  129.         }
  130.     }
  131.     else{
  132.  
  133.         if(valBitIndex==0)
  134.             return;
  135.  
  136.         int bit = (1<<(valBitIndex-1))&val;
  137.  
  138.         if(bit==0){//go right
  139.  
  140.             if(one[trieIndex]!=0){ //want to go right
  141.                 maxXOR(one[trieIndex],val,valBitIndex-1,appendZeroes);
  142.                 maxAns += (int)pow(2,valBitIndex-1);
  143.             }
  144.             else{
  145.                 maxXOR(zero[trieIndex],val,valBitIndex-1,appendZeroes);
  146.             }
  147.  
  148.         }
  149.         else{//go left
  150.             if(zero[trieIndex]!=0) { //want to go left
  151.                 maxXOR(zero[trieIndex],val,valBitIndex-1,appendZeroes);
  152.                 maxAns += (int)pow(2,valBitIndex-1);
  153.             }
  154.             else{
  155.                 maxXOR(one[trieIndex],val,valBitIndex-1,appendZeroes);
  156.             }
  157.         }
  158.  
  159.     }
  160.  
  161. }
  162.  
  163. void minXOR(int trieIndex,int val,int valBitIndex,int appendZeroes){
  164.  
  165.     if(appendZeroes>0){
  166.         if(zero[trieIndex]!=0){ //want to go left
  167.             minXOR(zero[trieIndex],val,valBitIndex,appendZeroes-1);
  168.         }
  169.         else{ //have to go right no choice left
  170.             minXOR(one[trieIndex],val,valBitIndex,appendZeroes-1);
  171.             minAns += (int)pow(2,valBitIndex+appendZeroes-1);
  172.         }
  173.     }
  174.     else{
  175.  
  176.         if(valBitIndex==0)
  177.             return;
  178.  
  179.         int bit = (1<<(valBitIndex-1))&val;
  180.  
  181.         if(bit==0){//go left
  182.  
  183.             if(zero[trieIndex]!=0){ //want to go left
  184.                 minXOR(zero[trieIndex],val,valBitIndex-1,appendZeroes);
  185.  
  186.             }
  187.             else{//have to go right no choice left
  188.                 minXOR(one[trieIndex],val,valBitIndex-1,appendZeroes);
  189.                 minAns += (int)pow(2,valBitIndex-1);
  190.             }
  191.  
  192.         }
  193.         else{//go right
  194.             if(one[trieIndex]!=0) { //want to go right
  195.                 minXOR(one[trieIndex],val,valBitIndex-1,appendZeroes);
  196.             }
  197.             else{//have to go left no choice left
  198.                 minXOR(zero[trieIndex],val,valBitIndex-1,appendZeroes);
  199.                 minAns += (int)pow(2,valBitIndex-1);
  200.             }
  201.         }
  202.  
  203.     }
  204.  
  205. }
  206.  
  207. int insert(int prevPointer,int val,int valBitIndex,int appendZeroes){
  208.  
  209.     if(appendZeroes>0){
  210.         return newNode(insert(zero[prevPointer],val,valBitIndex,appendZeroes-1),one[prevPointer]);
  211.     }
  212.     else{
  213.  
  214.         if(valBitIndex==0)
  215.             return newLeaf(val);
  216.  
  217.         int64 bit = (1<<(valBitIndex-1))&val;
  218.  
  219.         if(bit==0){//go left
  220.             return newNode(insert(zero[prevPointer],val,valBitIndex-1,appendZeroes),
  221.                            one[prevPointer]);
  222.         }
  223.         else{//go right
  224.             return newNode(zero[prevPointer],
  225.                            insert(one[prevPointer],val,valBitIndex-1,appendZeroes));
  226.         }
  227.  
  228.     }
  229.  
  230. }
  231.  
  232.  
  233.  
  234. void printTrie(int index){
  235.  
  236.     cout<<"node number: "<<index<<"\n";
  237.  
  238.     if(zero[index]==0 && one[index]==0) {
  239.         cout<<"leaf hit\n";
  240.         return;
  241.     }
  242.  
  243.     cout<<"going left\n";
  244.     printTrie(zero[index]);
  245.     cout<<"going right\n";
  246.     printTrie(one[index]);
  247.  
  248. }
  249.  
  250. void dfs(int p,int u){
  251.  
  252.     int v;
  253.     for (int i = 0; i < adj[u].size(); ++i) {
  254.         v = adj[u][i];
  255.         if(v!=p) {
  256.             int bitsCount = countBits(idToEncryption[v]);
  257.             //cout<<"current Node: "<<u<<" , parent node number = "<<idToNodeNumber[u]<<"\n";
  258.             int t = insert(idToNodeNumber[u],idToEncryption[v],bitsCount,LOGMAXN-bitsCount);
  259.             idToNodeNumber[v]=t;
  260.             dfs(u, v);
  261.         }
  262.     }
  263.  
  264. }
  265.  
  266.  
  267. void printDFS(int p, int64 u) {
  268.  
  269.     cout<<"NODE : "<<u<<"\n";
  270.     printTrie(idToNodeNumber[u]);
  271.     int v;
  272.     for (int i = 0; i < adj[u].size(); ++i) {
  273.         v = adj[u][i];
  274.         if(v!=p) {
  275.             printDFS(u, v);
  276.         }
  277.     }
  278. }
  279.  
  280.  
  281. int main()
  282. {
  283.  
  284.     MEM(zero,0);
  285.     MEM(one,0);
  286.     MEM(root,0);
  287.  
  288. #ifndef ONLINE_JUDGE
  289.     freopen("/Users/bhagirathi/Documents/CLionProjects/codeforces/debug/input.txt", "r", stdin);
  290.     freopen("/Users/bhagirathi/Documents/CLionProjects/codeforces/debug/output.txt", "w", stdout);
  291. #endif
  292.  
  293.     int n,q;
  294.     cin>>n>>q;
  295.  
  296.     int64 r,key;
  297.     cin>>r>>key;
  298.  
  299.     idToEncryption[r]=key;
  300.  
  301.     int64 u,v,k;
  302.     for (int i = 0; i <n-1 ; ++i) {
  303.  
  304.         cin>>u>>v>>k;
  305.  
  306.         VI currNeighbours = adj[v];
  307.         currNeighbours.push_back(u);
  308.         adj[v] = currNeighbours;
  309.  
  310.         idToEncryption[u]=k;
  311.     }
  312.  
  313. //    for (auto it = adj.begin(); it != adj.end() ; it++) {
  314. //
  315. //        cout<<" NODE: "<<it->first<<"\n";
  316. //        VI curr = it->second;
  317. //        for (int i = 0; i <curr.size() ; ++i) {
  318. //            cout<<curr[i]<<" ";
  319. //        }
  320. //        cout<<"\n";
  321. //
  322. //    }
  323.  
  324.     idToNodeNumber[0]=0;
  325.  
  326.     int bitsCount = countBits(key);
  327.     int t = insert(0,key,bitsCount,LOGMAXN-bitsCount);
  328.     idToNodeNumber[r] = t;
  329.  
  330.     dfs(0,r);
  331.  
  332.     //printDFS(0,r);
  333.  
  334.     int last_answer = 0;
  335.     for (int i = 0; i < q; i++)
  336.     {
  337.         cin >> t;
  338.  
  339.         // find real value of t
  340.         t ^= last_answer;
  341.  
  342.         if (t == 0)
  343.         {
  344.             cin >> v >> u >> k;
  345.  
  346.             // find real values for u, v, and k
  347.             u ^= last_answer;
  348.             v ^= last_answer;
  349.             k ^= last_answer;
  350.  
  351.             //insert
  352.             adj[v].push_back(u);
  353.             bitsCount = countBits(k);
  354.             idToEncryption[u]=k;
  355.             t = insert(idToNodeNumber[v],k,bitsCount,LOGMAXN-bitsCount);
  356.             idToNodeNumber[u] = t;
  357.  
  358.         }
  359.         else
  360.         {
  361.             cin >> v >> k;
  362.  
  363.             // find real values for v, and k
  364.             v ^= last_answer;
  365.             k ^= last_answer;
  366.  
  367.  
  368.             //cout<<"NODE NUMBER QUERY: "<<idToNodeNumber[v]<<"\n";
  369.  
  370.             // compute the requested values
  371.             bitsCount = countBits(k);
  372.             minXOR(idToNodeNumber[v],k,bitsCount,LOGMAXN-bitsCount);
  373.             int min_answer = minAns;
  374.             minAns = 0;
  375.             maxXOR(idToNodeNumber[v],k,bitsCount,LOGMAXN-bitsCount);
  376.             int max_answer = maxAns;
  377.             maxAns =0;
  378.  
  379.  
  380.             cout<<min_answer<<" "<<max_answer<<"\n";
  381.  
  382.             // update last_answer
  383.             last_answer = min_answer ^ max_answer;
  384.         }
  385.     }
  386.  
  387.     return 0;
  388. }
  389.  
  390.  
Success #stdin #stdout 0.02s 171520KB
comments (?)
stdin
copy 
6 4
1 2
5 1 3
2 1 4
3 2 5
4 2 1
6 3 3
1 4 2
6 0 12 0
7 12 7
4 0 7
stdout
copy 
0 6
2 7
0 1
https://ideone.com/LvIpJ1
language:
C++14 (gcc 8.3)
created:
5 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!