oj.uz

Submission #440851

# Submission time Handle Problem Language Result Execution time Memory
440851 2021-07-03T11:32:08 Z codebuster_10 Klasika (COCI20_klasika) C++17
110 / 110
 4732 ms 473460 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
 
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
 
#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))
 
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x;}
template<class H, class... T> void rd(H& h, T&... t) { rd(h); rd(t...);}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a);}
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0;}
 
template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}
 
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  // remove this when size of input is not fixed.
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}
 
 
/*********************************************Look Below******************************************************************/
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
const int MAX_N = 2e5 + 7;
vector<int> g[MAX_N], st(MAX_N), en(MAX_N), val(MAX_N);
 
int timer;
void dfs(int i){
  st[i] = timer++ ;
  for(auto j : g[i])	dfs(j);
  en[i] = timer - 1 ;
}
 
 
const int LOG = 31;
 
 
template<const int ALPHABET>
struct prefix_tree {
	
	struct trie_node {
  	int link[ALPHABET];
    set<int> whose;
 
    trie_node() {
      memset(link, -1, sizeof(link));
    }
	};
	
	vector<trie_node> trie;
	
	prefix_tree(){
		trie.emplace_back();
	}
	
	void create_node(int parent, int c) {
    trie.emplace_back();
	}
	
	int get_or_create_node(int current, int c) {
    if (trie[current].link[c] < 0) {
      trie[current].link[c] = trie.size();
      create_node(current, c);
    }
 
    return trie[current].link[c];
	}
 
	void insert_str(const int & x,const int & i) {
		int current = 0;
		for(int j = LOG - 1; j >= 0; --j){
			int c;
			if((x >> j) & 1){
				c = 1;
			}else{
				c = 0;
			}
			
			current = get_or_create_node(current,c);
			trie[current].whose.insert(i);
		}
    return;
	}
	
	// checks whether in trie[x].whose has some element b/w l,r;
	bool is(const int & x,const int & l,const int & r){
		auto itr = trie[x].whose.lower_bound(l);
		return itr != trie[x].whose.end() && (*itr) <= r;
	}
	
	int query(const int & x,const int & l,const int & r){
		int current = 0;
		
		int ans = 0;
		
		for(int j = LOG - 1; j >= 0; --j){
			int c;
			if((x >> j) & 1){
				c = 1;
			}else{
				c = 0;
			}
			
			int want = trie[current].link[!c];
			
			if(want > 0 && is(want,l,r)){
				ans ^= (1 << j);
				current = want;
			}else{
				current = trie[current].link[c];
				assert(current > 0 && is(current,l,r));
			}
		}
		return ans;
	}
};
 
prefix_tree<2> trie;
 
signed main(){
  setIO();
	int q; rd(q);
	vt<ar<int,3>> queries;
	
	val[1] = 0;
	int N = 1;
	while(q--){
		string s;
		rd(s);
		if(s == "Add"){
			int x,y;
			rd(x,y);
			g[x].pb(++N);
			val[N] = (val[x]^y);
			queries.pb({0,N,-1});
		}else if(s == "Query"){
			int a,b; rd(a,b);
			queries.pb({1,a,b});
		}else{
			assert(false);
		}
	}
	
	dfs(1);
	
	trie.insert_str(val[1],st[1]);
	for(auto [t,a,b] : queries){
		if(t){
			cout << trie.query(val[a],st[b],en[b]) << endl;
		}else{
			trie.insert_str(val[a],st[a]);
		}
	}
	
}

Compilation message

klasika.cpp: In function 'void setIO(std::string)':
klasika.cpp:82:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7756 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7756 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 5 ms 7756 KB Output is correct
12 Correct 5 ms 7756 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7756 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7756 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 5 ms 7756 KB Output is correct
12 Correct 5 ms 7756 KB Output is correct
13 Correct 8 ms 8832 KB Output is correct
14 Correct 10 ms 10404 KB Output is correct
15 Correct 12 ms 10656 KB Output is correct
16 Correct 15 ms 13472 KB Output is correct
17 Correct 9 ms 8808 KB Output is correct
18 Correct 11 ms 10384 KB Output is correct
19 Correct 13 ms 10656 KB Output is correct
20 Correct 14 ms 11552 KB Output is correct
21 Correct 9 ms 8808 KB Output is correct
22 Correct 10 ms 10296 KB Output is correct
23 Correct 12 ms 10528 KB Output is correct
24 Correct 16 ms 11552 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 118480 KB Output is correct
2 Correct 1709 ms 235512 KB Output is correct
3 Correct 2331 ms 288684 KB Output is correct
4 Correct 3124 ms 473328 KB Output is correct
5 Correct 1026 ms 119376 KB Output is correct
6 Correct 1856 ms 231812 KB Output is correct
7 Correct 2650 ms 283924 KB Output is correct
8 Correct 3476 ms 465840 KB Output is correct
9 Correct 944 ms 119788 KB Output is correct
10 Correct 1731 ms 232608 KB Output is correct
11 Correct 2382 ms 286472 KB Output is correct
12 Correct 3131 ms 467200 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7756 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7756 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 5 ms 7756 KB Output is correct
12 Correct 5 ms 7756 KB Output is correct
13 Correct 8 ms 8832 KB Output is correct
14 Correct 10 ms 10404 KB Output is correct
15 Correct 12 ms 10656 KB Output is correct
16 Correct 15 ms 13472 KB Output is correct
17 Correct 9 ms 8808 KB Output is correct
18 Correct 11 ms 10384 KB Output is correct
19 Correct 13 ms 10656 KB Output is correct
20 Correct 14 ms 11552 KB Output is correct
21 Correct 9 ms 8808 KB Output is correct
22 Correct 10 ms 10296 KB Output is correct
23 Correct 12 ms 10528 KB Output is correct
24 Correct 16 ms 11552 KB Output is correct
25 Correct 948 ms 118480 KB Output is correct
26 Correct 1709 ms 235512 KB Output is correct
27 Correct 2331 ms 288684 KB Output is correct
28 Correct 3124 ms 473328 KB Output is correct
29 Correct 1026 ms 119376 KB Output is correct
30 Correct 1856 ms 231812 KB Output is correct
31 Correct 2650 ms 283924 KB Output is correct
32 Correct 3476 ms 465840 KB Output is correct
33 Correct 944 ms 119788 KB Output is correct
34 Correct 1731 ms 232608 KB Output is correct
35 Correct 2382 ms 286472 KB Output is correct
36 Correct 3131 ms 467200 KB Output is correct
37 Correct 1788 ms 121840 KB Output is correct
38 Correct 2556 ms 236040 KB Output is correct
39 Correct 3026 ms 291208 KB Output is correct
40 Correct 3509 ms 473460 KB Output is correct
41 Correct 2036 ms 120040 KB Output is correct
42 Correct 2911 ms 232384 KB Output is correct
43 Correct 3451 ms 284064 KB Output is correct
44 Correct 4042 ms 466036 KB Output is correct
45 Correct 2139 ms 120352 KB Output is correct
46 Correct 3155 ms 233136 KB Output is correct
47 Correct 3852 ms 284952 KB Output is correct
48 Correct 4732 ms 467424 KB Output is correct