oj.uz

Submission #857374

# Submission time Handle Problem Language Result Execution time Memory
857374 2023-10-06T04:09:21 Z nnhzzz Klasika (COCI20_klasika) C++14
110 / 110
 2147 ms 437568 KB 
// -------------------------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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7568 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7564 KB Output is correct
7 Correct 2 ms 7600 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7768 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7568 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7564 KB Output is correct
7 Correct 2 ms 7600 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7768 KB Output is correct
13 Correct 4 ms 8540 KB Output is correct
14 Correct 6 ms 9900 KB Output is correct
15 Correct 7 ms 11100 KB Output is correct
16 Correct 8 ms 12380 KB Output is correct
17 Correct 4 ms 8540 KB Output is correct
18 Correct 6 ms 9940 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 8 ms 12376 KB Output is correct
21 Correct 5 ms 8540 KB Output is correct
22 Correct 6 ms 9888 KB Output is correct
23 Correct 7 ms 11100 KB Output is correct
24 Correct 8 ms 12380 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 125800 KB Output is correct
2 Correct 902 ms 233020 KB Output is correct
3 Correct 1262 ms 334616 KB Output is correct
4 Correct 1596 ms 436660 KB Output is correct
5 Correct 573 ms 125176 KB Output is correct
6 Correct 1024 ms 230648 KB Output is correct
7 Correct 1465 ms 331760 KB Output is correct
8 Correct 1938 ms 432936 KB Output is correct
9 Correct 554 ms 124152 KB Output is correct
10 Correct 954 ms 231212 KB Output is correct
11 Correct 1288 ms 333492 KB Output is correct
12 Correct 1644 ms 434520 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7568 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7564 KB Output is correct
7 Correct 2 ms 7600 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7768 KB Output is correct
13 Correct 4 ms 8540 KB Output is correct
14 Correct 6 ms 9900 KB Output is correct
15 Correct 7 ms 11100 KB Output is correct
16 Correct 8 ms 12380 KB Output is correct
17 Correct 4 ms 8540 KB Output is correct
18 Correct 6 ms 9940 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 8 ms 12376 KB Output is correct
21 Correct 5 ms 8540 KB Output is correct
22 Correct 6 ms 9888 KB Output is correct
23 Correct 7 ms 11100 KB Output is correct
24 Correct 8 ms 12380 KB Output is correct
25 Correct 559 ms 125800 KB Output is correct
26 Correct 902 ms 233020 KB Output is correct
27 Correct 1262 ms 334616 KB Output is correct
28 Correct 1596 ms 436660 KB Output is correct
29 Correct 573 ms 125176 KB Output is correct
30 Correct 1024 ms 230648 KB Output is correct
31 Correct 1465 ms 331760 KB Output is correct
32 Correct 1938 ms 432936 KB Output is correct
33 Correct 554 ms 124152 KB Output is correct
34 Correct 954 ms 231212 KB Output is correct
35 Correct 1288 ms 333492 KB Output is correct
36 Correct 1644 ms 434520 KB Output is correct
37 Correct 1044 ms 126712 KB Output is correct
38 Correct 1548 ms 232020 KB Output is correct
39 Correct 1758 ms 336884 KB Output is correct
40 Correct 1865 ms 437568 KB Output is correct
41 Correct 1142 ms 125436 KB Output is correct
42 Correct 1579 ms 230652 KB Output is correct
43 Correct 1937 ms 331804 KB Output is correct
44 Correct 2147 ms 432892 KB Output is correct
45 Correct 1239 ms 124964 KB Output is correct
46 Correct 1693 ms 230736 KB Output is correct
47 Correct 1948 ms 332288 KB Output is correct
48 Correct 2017 ms 434044 KB Output is correct