oj.uz

Submission #440854

# Submission time Handle Problem Language Result Execution time Memory
440854 2021-07-03T11:34:20 Z codebuster_10 Klasika (COCI20_klasika) C++17
110 / 110
 3799 ms 469576 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;
	}
	
	
	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];
			}
		}
		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 7532 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7804 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7744 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 7532 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7804 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7744 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 8788 KB Output is correct
14 Correct 10 ms 10276 KB Output is correct
15 Correct 12 ms 10664 KB Output is correct
16 Correct 14 ms 13324 KB Output is correct
17 Correct 8 ms 8808 KB Output is correct
18 Correct 11 ms 10276 KB Output is correct
19 Correct 13 ms 10528 KB Output is correct
20 Correct 13 ms 11424 KB Output is correct
21 Correct 8 ms 8808 KB Output is correct
22 Correct 10 ms 10276 KB Output is correct
23 Correct 13 ms 10492 KB Output is correct
24 Correct 14 ms 11476 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 118608 KB Output is correct
2 Correct 1703 ms 232420 KB Output is correct
3 Correct 2328 ms 285192 KB Output is correct
4 Correct 3109 ms 469576 KB Output is correct
5 Correct 1012 ms 116584 KB Output is correct
6 Correct 1828 ms 229004 KB Output is correct
7 Correct 2576 ms 280564 KB Output is correct
8 Correct 3427 ms 462104 KB Output is correct
9 Correct 941 ms 116948 KB Output is correct
10 Correct 1691 ms 229580 KB Output is correct
11 Correct 2345 ms 282652 KB Output is correct
12 Correct 3139 ms 463560 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 7532 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 5 ms 7804 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7744 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 8788 KB Output is correct
14 Correct 10 ms 10276 KB Output is correct
15 Correct 12 ms 10664 KB Output is correct
16 Correct 14 ms 13324 KB Output is correct
17 Correct 8 ms 8808 KB Output is correct
18 Correct 11 ms 10276 KB Output is correct
19 Correct 13 ms 10528 KB Output is correct
20 Correct 13 ms 11424 KB Output is correct
21 Correct 8 ms 8808 KB Output is correct
22 Correct 10 ms 10276 KB Output is correct
23 Correct 13 ms 10492 KB Output is correct
24 Correct 14 ms 11476 KB Output is correct
25 Correct 930 ms 118608 KB Output is correct
26 Correct 1703 ms 232420 KB Output is correct
27 Correct 2328 ms 285192 KB Output is correct
28 Correct 3109 ms 469576 KB Output is correct
29 Correct 1012 ms 116584 KB Output is correct
30 Correct 1828 ms 229004 KB Output is correct
31 Correct 2576 ms 280564 KB Output is correct
32 Correct 3427 ms 462104 KB Output is correct
33 Correct 941 ms 116948 KB Output is correct
34 Correct 1691 ms 229580 KB Output is correct
35 Correct 2345 ms 282652 KB Output is correct
36 Correct 3139 ms 463560 KB Output is correct
37 Correct 1470 ms 118488 KB Output is correct
38 Correct 2212 ms 232508 KB Output is correct
39 Correct 2775 ms 287408 KB Output is correct
40 Correct 3458 ms 469512 KB Output is correct
41 Correct 1751 ms 116624 KB Output is correct
42 Correct 2630 ms 228824 KB Output is correct
43 Correct 3184 ms 280464 KB Output is correct
44 Correct 3799 ms 462160 KB Output is correct
45 Correct 1806 ms 116892 KB Output is correct
46 Correct 2630 ms 229440 KB Output is correct
47 Correct 3089 ms 281180 KB Output is correct
48 Correct 3550 ms 463572 KB Output is correct