oj.uz

Submission #885132

# Submission time Handle Problem Language Result Execution time Memory
885132 2023-12-09T03:51:51 Z huynhyen1609 Klasika (COCI20_klasika) C++14
110 / 110
 2486 ms 423276 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME "andteddy"
//#define int long long
#define ii pair<int,int>
#define i(x) array<int,x>
const int N=2e5;
int q,n,pre[N+5],cnt,in[N+5],out[N+5];
vector<i(3)>vec;
vector<ii>graph[N+5];
int getbit(int x,int i)
{
    return (x>>i)&1;
}
void dfs(int u)
{
    in[u]=++cnt;
    for(ii v:graph[u])
    {
        pre[v.fi]=pre[u]^v.se;
        dfs(v.fi);
    }
    out[u]=cnt;
}
struct ta
{
    int c[2];
    set<int>s;
}trie[3000000];
void add(int u)
{
    int id=0;
    for(int i=30;i>=0;--i)
    {
        int tmp=getbit(pre[u],i);
        if(!trie[id].c[tmp])trie[id].c[tmp]=++cnt;
        id=trie[id].c[tmp];
        trie[id].s.insert(in[u]);
    }
}
int get(int u,int v)
{
    int id=0,res=pre[u];
    for(int i=30;i>=0;--i)
    {
        int t=0;
        int tmp=getbit(pre[u],i);
        if(trie[id].c[tmp^1])
        {
            int tm=trie[id].c[tmp^1];
            int l=*trie[tm].s.lower_bound(in[v]);
            if(l>=in[v]&&l<=out[v])
            {
                id=trie[id].c[tmp^1];
                res^=(tmp^1)<<i;
                t=1;
            }
        }
        if(trie[id].c[tmp]&&t!=1)
        {
            int tm=trie[id].c[tmp];
            int l=*trie[tm].s.lower_bound(in[v]);
            if(l>=in[v]&&l<=out[v])
            {
                id=trie[id].c[tmp];
                res^=tmp<<i;
            }
        }
    }
    return res;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen(""NAME".inp","r",stdin);
    //freopen(""NAME".out","w",stdout);
    cin>>q;
    n=1;
    for(int i=1;i<=q;++i)
    {
        string s;
        int u,v;
        cin>>s;
        cin>>u>>v;
        if(s=="Add")
        {
            vec.push_back({0,++n,0});
            graph[u].push_back({n,v});
        }
        else
        {
            vec.push_back({1,u,v});
        }
    }
    dfs(1);
    cnt=0;
    add(1);
    for(i(3)x:vec)
    {
        if(!x[0])add(x[1]);
        else cout<<get(x[1],x[2])<<'\n';
    }
}
/*
         ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/

Compilation message

klasika.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main()
      | ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 170832 KB Output is correct
2 Correct 37 ms 170936 KB Output is correct
3 Correct 39 ms 171348 KB Output is correct
4 Correct 36 ms 171092 KB Output is correct
5 Correct 43 ms 170832 KB Output is correct
6 Correct 36 ms 170844 KB Output is correct
7 Correct 36 ms 171088 KB Output is correct
8 Correct 36 ms 171096 KB Output is correct
9 Correct 37 ms 171132 KB Output is correct
10 Correct 38 ms 170836 KB Output is correct
11 Correct 37 ms 171092 KB Output is correct
12 Correct 37 ms 171092 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 170832 KB Output is correct
2 Correct 37 ms 170936 KB Output is correct
3 Correct 39 ms 171348 KB Output is correct
4 Correct 36 ms 171092 KB Output is correct
5 Correct 43 ms 170832 KB Output is correct
6 Correct 36 ms 170844 KB Output is correct
7 Correct 36 ms 171088 KB Output is correct
8 Correct 36 ms 171096 KB Output is correct
9 Correct 37 ms 171132 KB Output is correct
10 Correct 38 ms 170836 KB Output is correct
11 Correct 37 ms 171092 KB Output is correct
12 Correct 37 ms 171092 KB Output is correct
13 Correct 39 ms 171604 KB Output is correct
14 Correct 40 ms 172112 KB Output is correct
15 Correct 40 ms 172880 KB Output is correct
16 Correct 41 ms 173424 KB Output is correct
17 Correct 39 ms 171348 KB Output is correct
18 Correct 41 ms 172116 KB Output is correct
19 Correct 42 ms 172584 KB Output is correct
20 Correct 41 ms 173648 KB Output is correct
21 Correct 36 ms 171348 KB Output is correct
22 Correct 38 ms 172116 KB Output is correct
23 Correct 38 ms 172624 KB Output is correct
24 Correct 39 ms 173120 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 239292 KB Output is correct
2 Correct 935 ms 300568 KB Output is correct
3 Correct 1418 ms 361564 KB Output is correct
4 Correct 1802 ms 423088 KB Output is correct
5 Correct 512 ms 236764 KB Output is correct
6 Correct 1012 ms 296188 KB Output is correct
7 Correct 1544 ms 354556 KB Output is correct
8 Correct 2064 ms 414076 KB Output is correct
9 Correct 507 ms 236764 KB Output is correct
10 Correct 905 ms 297068 KB Output is correct
11 Correct 1370 ms 356948 KB Output is correct
12 Correct 1760 ms 415524 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 170832 KB Output is correct
2 Correct 37 ms 170936 KB Output is correct
3 Correct 39 ms 171348 KB Output is correct
4 Correct 36 ms 171092 KB Output is correct
5 Correct 43 ms 170832 KB Output is correct
6 Correct 36 ms 170844 KB Output is correct
7 Correct 36 ms 171088 KB Output is correct
8 Correct 36 ms 171096 KB Output is correct
9 Correct 37 ms 171132 KB Output is correct
10 Correct 38 ms 170836 KB Output is correct
11 Correct 37 ms 171092 KB Output is correct
12 Correct 37 ms 171092 KB Output is correct
13 Correct 39 ms 171604 KB Output is correct
14 Correct 40 ms 172112 KB Output is correct
15 Correct 40 ms 172880 KB Output is correct
16 Correct 41 ms 173424 KB Output is correct
17 Correct 39 ms 171348 KB Output is correct
18 Correct 41 ms 172116 KB Output is correct
19 Correct 42 ms 172584 KB Output is correct
20 Correct 41 ms 173648 KB Output is correct
21 Correct 36 ms 171348 KB Output is correct
22 Correct 38 ms 172116 KB Output is correct
23 Correct 38 ms 172624 KB Output is correct
24 Correct 39 ms 173120 KB Output is correct
25 Correct 529 ms 239292 KB Output is correct
26 Correct 935 ms 300568 KB Output is correct
27 Correct 1418 ms 361564 KB Output is correct
28 Correct 1802 ms 423088 KB Output is correct
29 Correct 512 ms 236764 KB Output is correct
30 Correct 1012 ms 296188 KB Output is correct
31 Correct 1544 ms 354556 KB Output is correct
32 Correct 2064 ms 414076 KB Output is correct
33 Correct 507 ms 236764 KB Output is correct
34 Correct 905 ms 297068 KB Output is correct
35 Correct 1370 ms 356948 KB Output is correct
36 Correct 1760 ms 415524 KB Output is correct
37 Correct 1010 ms 239868 KB Output is correct
38 Correct 1487 ms 300804 KB Output is correct
39 Correct 1901 ms 363100 KB Output is correct
40 Correct 2208 ms 423276 KB Output is correct
41 Correct 1164 ms 237788 KB Output is correct
42 Correct 1691 ms 297036 KB Output is correct
43 Correct 2126 ms 354716 KB Output is correct
44 Correct 2486 ms 413632 KB Output is correct
45 Correct 1217 ms 237276 KB Output is correct
46 Correct 1880 ms 297532 KB Output is correct
47 Correct 2079 ms 356780 KB Output is correct
48 Correct 2296 ms 416120 KB Output is correct