Submission #891753

#	Time	Username	Problem	Language	Result	Execution time	Memory
891753		Fucsdeptrai	Klasika (COCI20_klasika)	C++17	33 / 110	522 ms	524288 KiB

klasika

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 9;
const int Log = 30;

struct Node
{
    Node *c[2];
    int mn;

    Node()
    {
        c[0] = c[1] = NULL;
        mn = N;
    }
};

int n, q, Timer;
vector<pair<int, int>> adj[N];
int num[N], tail[N], pos[N], d[N];
vector<pair<pair<int, int>, int>> vt;
vector<pair<int, int>> vec[N*4];
Node *Trie[N*4];

void Add(int id, int x, int y)
{
    Node *p = Trie[id];
    for(int i = Log; i >= 0;i --)
    {
        bool w = (1<<i)&x;
        if(p->c[w] == NULL) p->c[w] = new Node;
        p = p->c[w];
        p->mn = min(p->mn, y);
    }
}

int Get(int id, int x, int y)
{
    Node *p = Trie[id];
    for(int i = Log; i >= 0;i --)
    {
        bool w = (1<<i)&x;
        if(p->c[w^1] != NULL and p->c[w^1]->mn <= y)
        {
            x ^= ((w^1)<<i);
            p = p->c[w^1];
        }
        else if(p->c[w] != NULL and p->c[w]->mn <= y)
        {
            x ^= (w<<i);
            p = p->c[w];
        }
        else
        {
            return 0;
        }
    }
    return x;
}

void Dfs(int u = 1, int du = 0)
{
    num[u] = ++ Timer;
    d[u] = du;
    pos[Timer] = u;
    for(auto [v, w] : adj[u])
    {
        Dfs(v, du^w);
    }
    tail[u] = Timer;
}

void Build(int id = 1, int l = 1, int r = n)
{
    if(l==r)
    {
        Trie[id] = new Node();
        Add(id, d[pos[l]], pos[l]);
        vec[id].push_back({d[pos[l]], pos[l]});
        return ;
    }

    int mid = l+r>>1;
    Build(id<<1, l, mid);
    Build(id<<1|1, mid+1, r);
    vec[id].resize(vec[id<<1].size() + vec[id<<1|1].size());
    merge(vec[id<<1].begin(), vec[id<<1].end(), vec[id<<1|1].begin(), vec[id<<1|1].end(), vec[id].begin());
    Trie[id] = new Node();
    int lst = -1;
    for(auto [x, y] : vec[id])
    {
        if(x==lst) continue;
        Add(id, x, y);
        lst = x;
    }
}

int Get(int L, int R, int x, int y, int id = 1, int l = 1, int r = n)
{
    if(l>r or l>R or L>r) return 0;
    if(L<=l and r<=R) return Get(id, x, y);

    int mid = l+r>>1;
    return max(Get(L, R, x, y, id<<1, l, mid), Get(L, R, x, y, id<<1|1, mid+1, r));
}

void Solve()
{
    cin>>q;
    ++n;
    while(q--)
    {
        string Type; cin>>Type;
        int x, y; cin >> x >> y;
        if(Type == "Add")
        {
            adj[x].push_back({++n, y});
        }
        else
        {
            vt.push_back({{x, y}, n});
        }
    }

    Timer = 0;
    Dfs();
    Build();

    for(auto [uv, w] : vt)
    {
        auto [u, v] = uv;
        cout << Get(num[v], tail[v], d[u], w) << '\n';
    }
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int TC = 1;
//	cin>>TC;
    while(TC--)
    {
        Solve();
    }
}

Compilation message (stderr)

klasika.cpp: In function 'void Build(int, int, int)':
klasika.cpp:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int mid = l+r>>1;
      |               ~^~
klasika.cpp: In function 'int Get(int, int, int, int, int, int, int)':
klasika.cpp:106:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = l+r>>1;
      |               ~^~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44