oj.uz

Submission #891759

# Submission time Handle Problem Language Result Execution time Memory
891759 2023-12-24T02:33:38 Z Fucsdeptrai Klasika (COCI20_klasika) C++17
0 / 110
 324 ms 126308 KB 
#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, m, q, Timer;
int d[N], res[N];
vector<pair<int, int>> adj[N], vec[N];
vector<pair<pair<int, int>, int>> que[N];
Node *Trie[N];

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);
    }
}

void Remove(Node *p)
{
    if(p->c[0] != NULL) Remove(p->c[0]);
    if(p->c[1] != NULL) Remove(p->c[1]);
    delete p;
}

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)
{
    d[u] = du;
    for(auto [v, w] : adj[u])
    {
        Dfs(v, du^w);
    }
}

void Merge(int u, int v)
{
    if(vec[u].size() < vec[v].size()) swap(vec[u], vec[v]);
    for(auto x : vec[v]) vec[u].push_back(x);
}

void Dfs1(int u = 1)
{
    vec[u].push_back({d[u], u});
    int bigC = -1;
    for(auto [v, w] : adj[u])
    {
        Dfs1(v);
        if(bigC == -1) bigC = v;
        else if(vec[v].size() > vec[bigC].size()) bigC = v;
    }

    if(bigC == -1) Trie[u] = new Node();
    else
    {
        Trie[u] = Trie[bigC];
        vec[u] = vec[bigC];
        vec[bigC].clear();
    }
    Add(u, d[u], u);

    for(auto [v, w] : adj[u])
    {
        if(v == bigC) continue;
        for(auto [x, y] : vec[v])
        {
            Add(u, x, y);
            vec[u].push_back({x, y});
        }
        Remove(Trie[v]);
        vec[v].clear();
    }

    for(auto [xy, id] : que[u])
    {
        auto [x, y] = xy;
        res[id] = Get(u, d[x], y);
    }
}

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
        {
            que[y].push_back({{x, n}, ++m});
        }
    }

    Timer = 0;
    Dfs();
    Dfs1();
    for(int i = 1;i <= m; i++)
    {
        cout << res[i] << '\n';
    }
}

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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Incorrect 4 ms 16728 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Incorrect 4 ms 16728 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 48876 KB Output is correct
2 Correct 238 ms 77900 KB Output is correct
3 Correct 265 ms 101980 KB Output is correct
4 Correct 290 ms 126308 KB Output is correct
5 Incorrect 324 ms 39900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Incorrect 4 ms 16728 KB Output isn't correct
6 Halted 0 ms 0 KB -