Submission #857374

#	Time	Username	Problem	Language	Result	Execution time	Memory
857374		nnhzzz	Klasika (COCI20_klasika)	C++14	110 / 110	2147 ms	437568 KiB

klasika

// -------------------------Solution by Stormgamming------------------------- //
/* Author: Nguyen Ngoc Hung, Ngo Gia Tu high school */

/*
tips
  1.int? long long?
  2.don't submit wrong answer
  3.figure out logic first, then start writing please
  4.know about the range
  5.check if you have to input t or not
  6.modulo of negative numbers is not a%b, it is a%b + abs(b)
  7.special cases (n=1?)
*/

//-------------------------------------------------------------//
// #include <algorithm>
// #include <bitset>
// #include <complex>
// #include <deque>
// #include <exception>
// #include <fstream>
// #include <functional>
// #include <iomanip>
// #include <ios>
// #include <iosfwd>
#include <iostream>
// #include <istream>
// #include <iterator>
// #include <limits>
// #include <list>
// #include <locale>
// #include <map>
// #include <memory>
// #include <new>
// #include <numeric>
// #include <ostream>
// #include <queue>
#include <set>
// #include <sstream>
// #include <stack>
// #include <stdexcept>
// #include <streambuf>
// #include <string>
// #include <typeinfo>
// #include <utility>
// #include <valarray>
#include <vector>
// #include <cstring>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

//-------------------------------------------------------------//

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
#pragma GCC optimize("Ofast")


//-------------------------------------------------------------//
#define __Stormgamming__ signed main()
// #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
// #define repdis(i,be,en,j) for(int i = (be); i<=(en); i+=j)
// #define repd(i,be,en) for(int i = (be); i>=(en); i--)
// #define rep(i,be,en) for(int i = (be); i<=(en); i++)
// #define reset(x,val) memset((x),(val),sizeof(x))
#define file(name) if(fopen(name".inp", "r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
// #define DEBUG(X) {auto _X=(X); cerr << "L" << __LINE__ << ": " << #X << " = " << (_X) << endl;}
// #define debug(x) cerr << #x << " = " << (x) << '\n'
// #define bit(i,j) ((i>>j)&1ll)
#define mask(i) (1ll<<i)
// #define all(x) (x).begin(),(x).end()
// #define sz(x) (int)(x).size()
// #define vvvi vector<vector<vector<int>>>
#define vpii vector<pair<int,int>>
// #define piii pair<int,pii>
// #define vvi vector<vector<int>>
// #define vi vector<int>
// #define pii pair<int,int>
// #define inf 0x3f3f3f3f
// #define pii pair<int,int>
// #define endl "\n"
// #define ull unsigned long long
// #define ll long long
// #define ld long double
// #define int long long
#define fi first
#define se second

//-------------------------IOS----------------------------------//
// inline void scan(){} template<typename F, typename... R> inline void scan(F &f,R&... r){cin>>f;scan(r...);}
// inline void print(){} template<typename F, typename... R> inline void print(F f,R... r){cout<<f;print(r...);}

//-------------------------------------------------------------//
// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
// template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}

//-------------------------------------------------------------//
// bool mem2;
// const int N = (int)1e6+1;
// const int SIZE = (int)1e6+10;
const int maxn = (int)2e5+1;
// const int MOD = (int)1e9+7;
// const int oo = (int)1e18+7;
// const int base = (int)311;
// const ld PI = (ld)3.1415926535897932384626433832795;

//-------------------------------------------------------------//
// int dx[] = {-1, 1, 0, 0};
// int dy[] = {0, 0, -1, 1};

struct QUERY{
	bool ok;
	int u,v;

	QUERY(bool _ok, int _u, int _v):ok(_ok),u(_u),v(_v){}
};

struct Node{
	set<int> s;
	Node *a[2];

	Node(){
		a[0] = a[1] = NULL;
	}
}root;

vector<QUERY> qu;
vpii adj[maxn];
int tin[maxn],tout[maxn],sxor[maxn];
int q,time_dfs = 0;

void dfs(int u, int dad, int val){
	tin[u] = ++time_dfs;
	sxor[u] = val;
	for(auto [v,w]:adj[u]){
		if(v==dad){
			continue;
		}
		dfs(v,u,w xor val);
	}
	tout[u] = time_dfs;
}

void addtrie(Node *node, int bit, int val, int id){
	node->s.insert(id);
	if(bit<0){
		return ;
	}
	if(node->a[val>>bit&1]==NULL){
		node->a[val>>bit&1] = new Node();
	}
	addtrie(node->a[val>>bit&1],bit-1,val,id);
}

int gettrie(Node *node, int bit, int val, int l, int r){
	if(bit<0){
		return 0;
	}
	int id = ((val>>bit)&1) xor 1,res = 0;
	// auto it1 = node->a[id]->s.lower_bound(l);
	// auto it2 = node->a[id]->s.upper_bound(r);
	// if(node->a[id]==NULL || node->a[id]->s.lower_bound(l)==node->a[id]->s.upper_bound(r)){
	// 	return gettrie(node->a[id xor 1],bit-1,val,l,r);
	// }else{
	// 	return mask(bit)+gettrie(node->a[id],bit-1,val,l,r);
	// }
	if(node->a[id]==NULL){
		id = id xor 1;
	}else{
		auto cur = node->a[id]->s.lower_bound(l);
		if(cur==node->a[id]->s.end() || *cur>r){
			id = id xor 1;
		}
	}
	// id = id xor 1;
	if(node->a[id]==NULL){
		return 0;
	}else{
		auto cur = node->a[id]->s.lower_bound(l);
		if(cur==node->a[id]->s.end() || *cur>r){
			return 0;
		}
	}
	return id*mask(bit)|gettrie(node->a[id],bit-1,val,l,r);
}

void solve(){
	int n = 1;
	scanf("%d",&q);
	while(q--){
		char s[10];
    	scanf("%s",s);
		if(s[0]=='A'){
			int u,w;
			scanf("%d%d",&u,&w);
			u--;
			qu.push_back(QUERY(false,n,w));
			adj[u].push_back({n,w});
			adj[n].push_back({u,w});
			n++;
		}else{
			int u,v;
			scanf("%d%d",&u,&v);
			u--; v--;
			qu.push_back(QUERY(true,u,v));
		}
	}
	dfs(0,-1,0);
	addtrie(&root,30,0,tin[0]);
	for(auto &cur:qu){
		int u = cur.u;
		int v = cur.v;
		if(cur.ok==false){
			addtrie(&root,30,sxor[u],tin[u]);
		}else{
			printf("%d\n",gettrie(&root,30,sxor[u],tin[v],tout[v]) xor sxor[u]);
		}
	}
}

// bool mem1;
//-------------------------------------------------------------//
__Stormgamming__{
  // ios::sync_with_stdio(0);
  // cin.tie(0); cout.tie(0);
  // ios_base::sync_with_stdio(0);
  // cin.tie(NULL); cout.tie(NULL);
  if(fopen("Input.inp","r")){
    freopen("Input.inp","r",stdin);
    freopen("Output.out","w",stdout);
  }

  int test = 1;
  bool tests = 0;

  // if(tests==1) scan(test);
  // cin >> test;
  while(test--){
    solve();
    // print("testcase ",i,": ",endl);
  }

  //-------------------------------------------------------------//
  // cerr << "Memory Cost: " << abs(&mem1-&mem2)/1024./1024. << "MB" << endl;
  cerr << "Time Cost: " << clock()*1000./CLOCKS_PER_SEC << "MS" << endl;
  return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >AC \>AC
**/

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int, int)':
klasika.cpp:138:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |  for(auto [v,w]:adj[u]){
      |           ^
klasika.cpp: In function 'int gettrie(Node*, int, int, int, int)':
klasika.cpp:162:32: warning: unused variable 'res' [-Wunused-variable]
  162 |  int id = ((val>>bit)&1) xor 1,res = 0;
      |                                ^~~
klasika.cpp: In function 'int main()':
klasika.cpp:237:8: warning: unused variable 'tests' [-Wunused-variable]
  237 |   bool tests = 0;
      |        ^~~~~
klasika.cpp: In function 'void solve()':
klasika.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
klasika.cpp:195:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |      scanf("%s",s);
      |      ~~~~~^~~~~~~~
klasika.cpp:198:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |    scanf("%d%d",&u,&w);
      |    ~~~~~^~~~~~~~~~~~~~
klasika.cpp:206:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |    scanf("%d%d",&u,&v);
      |    ~~~~~^~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:232:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |     freopen("Input.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:233:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |     freopen("Output.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44