oj.uz

Submission #891761

# Submission time Handle Problem Language Result Execution time Memory
891761 2023-12-24T02:37:25 Z Fucsdeptrai Klasika (COCI20_klasika) C++17
33 / 110
 426 ms 524288 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)
{
    vec[id].push_back({x, 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)
{
    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);
        }
        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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 4 ms 16848 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 4 ms 16732 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 4 ms 16848 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 4 ms 16732 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 6 ms 19032 KB Output is correct
14 Correct 9 ms 23292 KB Output is correct
15 Correct 11 ms 30044 KB Output is correct
16 Correct 16 ms 37804 KB Output is correct
17 Correct 7 ms 17240 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 10 ms 18012 KB Output is correct
20 Correct 9 ms 18300 KB Output is correct
21 Correct 6 ms 17240 KB Output is correct
22 Correct 7 ms 18204 KB Output is correct
23 Correct 9 ms 19548 KB Output is correct
24 Correct 10 ms 21592 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 426 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 4 ms 16848 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 4 ms 16732 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 6 ms 19032 KB Output is correct
14 Correct 9 ms 23292 KB Output is correct
15 Correct 11 ms 30044 KB Output is correct
16 Correct 16 ms 37804 KB Output is correct
17 Correct 7 ms 17240 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 10 ms 18012 KB Output is correct
20 Correct 9 ms 18300 KB Output is correct
21 Correct 6 ms 17240 KB Output is correct
22 Correct 7 ms 18204 KB Output is correct
23 Correct 9 ms 19548 KB Output is correct
24 Correct 10 ms 21592 KB Output is correct
25 Runtime error 426 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -