oj.uz

Submission #1116384

# Submission time Handle Problem Language Result Execution time Memory
1116384 2024-11-21T14:48:10 Z 8pete8 Klasika (COCI20_klasika) C++17
110 / 110
 2694 ms 190508 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mxn=2e5+5,lg=30,inf=1e9,minf=-1e9;
int n,q;
vector<pair<int,pii>>qry;
vector<pii>adj[mxn+10];
int tin[mxn+10],tout[mxn+10],T=0,dist[mxn+10];
void dfs(int cur,int p){
	tin[cur]=++T;
	for(auto i:adj[cur])if(i.f!=p){
		dist[i.f]=dist[cur]^i.s;
		dfs(i.f,cur);
	}
	tout[cur]=T;
}
struct mst{
	set<int>v[2*mxn+10];
	void update(int pos,int val){
		pos+=n;
		v[pos].insert(val);
		for(int i=pos;i>0;i>>=1)v[i>>1].insert(val);
	}
	int check(int pos,int x,int y){
		auto it=v[pos].lb(x);
		if(it==v[pos].end())return 0;
		return (*it)<=y;
	}
	int qry(int l,int r,int x,int y){
		int have=0;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l&1)have|=check(l++,x,y);
			if(!(r&1))have|=check(r--,x,y);
			if(have)return have;
		}
		return have;
	}
}t;
int32_t main(){
	fastio
	cin>>q;
	n=1;
	for(int i=0;i<q;i++){
		string a;cin>>a;
		int x,y;cin>>x>>y;
		if(a[0]=='A'){
			n++;
			qry.pb({1,{n,y}});
			adj[n].pb({x,y});
			adj[x].pb({n,y});
		}
		else qry.pb({0,{x,y}});
	}
	dfs(1,-1);
	t.update(1,0);
	for(int i=0;i<q;i++){
		if(qry[i].f)t.update(tin[qry[i].s.f],dist[qry[i].s.f]);
		else{
			int cur=0;
			for(int k=30;k>=0;k--){
				if(!(dist[qry[i].s.f]&(1LL<<k))){
					//trying to get 1
					cur+=(1LL<<k);
					if(!t.qry(tin[qry[i].s.s],tout[qry[i].s.s],cur,cur+(1LL<<k)-1))cur-=(1LL<<k);
				}
				else{
					if(!t.qry(tin[qry[i].s.s],tout[qry[i].s.s],cur,cur+(1LL<<k)-1))cur+=(1LL<<k);
				}
			}
			cout<<(dist[qry[i].s.f]^cur)<<'\n';
		}
	}
}
/*
basically given a value x
find a value y in rang [l,r] where x^y is maximum

try fixing bit
let say we fix suffix(most sig bit) to be XXX1001
and the X are not fix
the min value is 0001001 and max value is 1111001
to see if there exist a value with this suffix 
just check if theres a value between 0001001 and 1111001
merge sort tree on euler tour?
each update = log^2(n)
qry =log^3(n)
x=add,y=qry
y=2e5-x;
xlog^2(x) + ylog^2(x)30
xlog^2(x)+(2e5-x)log^2(x)30
worst case x=33,300 y=1e8
should pass??
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28496 KB Output is correct
2 Correct 6 ms 28496 KB Output is correct
3 Correct 6 ms 28664 KB Output is correct
4 Correct 6 ms 28496 KB Output is correct
5 Correct 7 ms 28496 KB Output is correct
6 Correct 6 ms 28496 KB Output is correct
7 Correct 5 ms 26448 KB Output is correct
8 Correct 6 ms 28496 KB Output is correct
9 Correct 6 ms 28664 KB Output is correct
10 Correct 6 ms 24656 KB Output is correct
11 Correct 5 ms 24832 KB Output is correct
12 Correct 8 ms 24824 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28496 KB Output is correct
2 Correct 6 ms 28496 KB Output is correct
3 Correct 6 ms 28664 KB Output is correct
4 Correct 6 ms 28496 KB Output is correct
5 Correct 7 ms 28496 KB Output is correct
6 Correct 6 ms 28496 KB Output is correct
7 Correct 5 ms 26448 KB Output is correct
8 Correct 6 ms 28496 KB Output is correct
9 Correct 6 ms 28664 KB Output is correct
10 Correct 6 ms 24656 KB Output is correct
11 Correct 5 ms 24832 KB Output is correct
12 Correct 8 ms 24824 KB Output is correct
13 Correct 9 ms 24912 KB Output is correct
14 Correct 13 ms 25168 KB Output is correct
15 Correct 10 ms 25424 KB Output is correct
16 Correct 12 ms 25880 KB Output is correct
17 Correct 11 ms 24928 KB Output is correct
18 Correct 8 ms 25336 KB Output is correct
19 Correct 13 ms 25424 KB Output is correct
20 Correct 17 ms 25680 KB Output is correct
21 Correct 10 ms 24812 KB Output is correct
22 Correct 10 ms 25168 KB Output is correct
23 Correct 9 ms 27216 KB Output is correct
24 Correct 11 ms 25780 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 67536 KB Output is correct
2 Correct 1111 ms 109804 KB Output is correct
3 Correct 1100 ms 148484 KB Output is correct
4 Correct 1173 ms 190508 KB Output is correct
5 Correct 1350 ms 67860 KB Output is correct
6 Correct 1808 ms 105880 KB Output is correct
7 Correct 2499 ms 147440 KB Output is correct
8 Correct 2694 ms 187032 KB Output is correct
9 Correct 1220 ms 66524 KB Output is correct
10 Correct 1452 ms 106156 KB Output is correct
11 Correct 1474 ms 146436 KB Output is correct
12 Correct 1444 ms 189676 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28496 KB Output is correct
2 Correct 6 ms 28496 KB Output is correct
3 Correct 6 ms 28664 KB Output is correct
4 Correct 6 ms 28496 KB Output is correct
5 Correct 7 ms 28496 KB Output is correct
6 Correct 6 ms 28496 KB Output is correct
7 Correct 5 ms 26448 KB Output is correct
8 Correct 6 ms 28496 KB Output is correct
9 Correct 6 ms 28664 KB Output is correct
10 Correct 6 ms 24656 KB Output is correct
11 Correct 5 ms 24832 KB Output is correct
12 Correct 8 ms 24824 KB Output is correct
13 Correct 9 ms 24912 KB Output is correct
14 Correct 13 ms 25168 KB Output is correct
15 Correct 10 ms 25424 KB Output is correct
16 Correct 12 ms 25880 KB Output is correct
17 Correct 11 ms 24928 KB Output is correct
18 Correct 8 ms 25336 KB Output is correct
19 Correct 13 ms 25424 KB Output is correct
20 Correct 17 ms 25680 KB Output is correct
21 Correct 10 ms 24812 KB Output is correct
22 Correct 10 ms 25168 KB Output is correct
23 Correct 9 ms 27216 KB Output is correct
24 Correct 11 ms 25780 KB Output is correct
25 Correct 806 ms 67536 KB Output is correct
26 Correct 1111 ms 109804 KB Output is correct
27 Correct 1100 ms 148484 KB Output is correct
28 Correct 1173 ms 190508 KB Output is correct
29 Correct 1350 ms 67860 KB Output is correct
30 Correct 1808 ms 105880 KB Output is correct
31 Correct 2499 ms 147440 KB Output is correct
32 Correct 2694 ms 187032 KB Output is correct
33 Correct 1220 ms 66524 KB Output is correct
34 Correct 1452 ms 106156 KB Output is correct
35 Correct 1474 ms 146436 KB Output is correct
36 Correct 1444 ms 189676 KB Output is correct
37 Correct 1050 ms 71892 KB Output is correct
38 Correct 1380 ms 107540 KB Output is correct
39 Correct 1486 ms 149288 KB Output is correct
40 Correct 1436 ms 190444 KB Output is correct
41 Correct 435 ms 67672 KB Output is correct
42 Correct 869 ms 105684 KB Output is correct
43 Correct 1314 ms 147288 KB Output is correct
44 Correct 1759 ms 186320 KB Output is correct
45 Correct 501 ms 66288 KB Output is correct
46 Correct 774 ms 106016 KB Output is correct
47 Correct 1000 ms 145640 KB Output is correct
48 Correct 1176 ms 187416 KB Output is correct