oj.uz

Submission #336399

# Submission time Handle Problem Language Result Execution time Memory
336399 2020-12-15T07:55:02 Z AriaH Klasika (COCI20_klasika) C++11
0 / 110
 1303 ms 519604 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 2e5 + 10;
const int M = 8e6;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 30;

char C[N];

int q, n = 1, ptr, Cnt = 1, L[M], R[M], w[N], St[N], Fi[N], yal[N];

set < int > st[M];

vector < int > G[N];

pair < string, pii > Q[N];

void dfs(int v)
{
    St[v] = ++ptr;
    for(auto u : G[v])
    {
	w[u] = w[v] ^ yal[u];
	dfs(u);
    }
    Fi[v] = ptr;
}

inline void okl(int v)
{
    if(L[v] == -1) L[v] = ++Cnt;
}

inline void okr(int v)
{
    if(R[v] == -1) R[v] = ++Cnt;
}

void add_trie(int v, int T, int node)
{
    st[v].insert(St[node]);
    if(T == -1) return;
    if(w[node] >> T & 1)
    {
	okr(v);
	add_trie(R[v], T - 1, node);
    }
    else
    {
	okl(v);
	add_trie(L[v], T - 1, node);
    }
}

bool check(int v, int node)
{
    auto it = st[v].lower_bound(St[node]);
    if(it == st[v].end() || *it > Fi[node]) return 0;
    return 1;
}

int ask_trie(int v, int T, int x, int node)
{
    if(T == -1) return 0;
    okl(v);
    okr(v);
    if(x >> T & 1)
    {
	if(check(L[v], node) == 1) return (1 << T) + ask_trie(L[v], T - 1, x, node);
	return ask_trie(R[v], T - 1, x, node);
    }
    else
    {
	if(check(R[v], node) == 1) return (1 << T) + ask_trie(R[v], T - 1, x, node);
	return ask_trie(L[v], T - 1, x, node);
    }
}

int main()
{
    memset(L, -1, sizeof L), memset(R, -1, sizeof R);
    scanf("%d", &q);
    for(int i = 1; i <= q; i ++)
    {
	string s;
	int a, b;
	scanf("%s%d%d", C, &a, &b);
	s = C;
	Q[i] = Mp(s, Mp(a, b));
	if(s == "Add")
	{
	    ++n;
	    G[a].push_back(n);
	    yal[n] = b;
	}
    }
    dfs(1);
    int _n = 1;
    for(int i = 1; i <= q; i ++)
    {
	if(Q[i].F == "Add")
	{
	    _n ++;
	    add_trie(1, LOG, _n);
	}
	else
	{
	    printf("%d\n", ask_trie(1, LOG, w[Q[i].S.F], Q[i].S.S));
	}
    }
    return 0;
}
/*!
        stay away from negative people they have a problem for every solution !
*/
/*
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1 
*/

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
klasika.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |  scanf("%s%d%d", C, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 451328 KB Output is correct
2 Incorrect 255 ms 451308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 451328 KB Output is correct
2 Incorrect 255 ms 451308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1303 ms 519604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 451328 KB Output is correct
2 Incorrect 255 ms 451308 KB Output isn't correct
3 Halted 0 ms 0 KB -