oj.uz

답안 #769563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769563 2023-06-29T19:19:22 Z MohamedAliSaidane Klasika (COCI20_klasika) C++14
33 / 110
 403 ms 260696 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()

const int nax = 2e5 + 4;
int q, n = 1, k = 1;
int sp[nax][20], d[nax], dep[nax], eul[nax], eulend[nax];
int cureul = -1;
vector<pii> adj[nax];
struct node
{
    int layer = 0;
    node *zer, *one;
    node(): layer(0), zer(nullptr), one(nullptr){}
    node (int d, node *ll, node *rr)
    {
        zer = ll, one = rr;
        layer= d;
    }
    node(node *cp): layer(cp->layer), zer(cp->zer), one(cp->one) {}
};
node *update(node *Node, int val, int d)
{
    if(d == 0)
        return new node();
    if(val & (1 << (d - 1)))
    {
        if(Node->one == nullptr)
            Node->one = new node(d - 1, nullptr, nullptr);
        return new node(d, Node->zer, update(Node->one, val, d - 1));

    }
    else
    {
        if(Node->zer == nullptr)
            Node->zer = new node(d - 1, nullptr, nullptr);
        return new node(d, update(Node->zer, val, d - 1), Node->one);
    }
}
node *roots[4 * nax];

int query(node *Node, int val)
{

    if(Node->layer == 0)
        return 0;
   // cout << Node->layer << ' ' << val << '\n';
    if(val & (1 << (Node->layer - 1)))
    {
        if(Node->zer != nullptr)
            return (1 << (Node->layer - 1)) + query(Node->zer, val);
        else
            return query(Node->one, val);
    }
    else
    {
        if(Node->one != nullptr)
            return (1 << (Node->layer - 1)) + query(Node->one, val);
        else
            return query(Node->zer, val);
    }
}
void pupd(int i, int val)
{
    i += k;
    if(roots[i] == nullptr)
        roots[i] = new node(30, nullptr, nullptr);
    roots[i] = update(roots[i], val, 30);
   // cout << i << endl;
    i /= 2;

    while(i)
    {
        //cout << i << endl;
        if(roots[i] == nullptr)
        roots[i] = new node(30, nullptr, nullptr);
        roots[i] = update(roots[i], val, 30);
        i /= 2;
    }
}
int squery(int p, int l, int r, int i, int j, int val)
{
    if(i > j)
        return 0;
    if(l >= i && r <= j)
    {
        if(roots[p] != nullptr)
            return query(roots[p], val);
        else
            return 0;
    }
    int m = (l + r)/2;
    return max(squery(2 * p, l, m, i, min(j, m), val),
               squery(2 * p + 1, m + 1, r, max(i, m + 1), j, val));
}
void dfs(int x, int p)
{
    eul[x] = ++cureul;
    sp[x][0] = p;
    for(auto e: adj[x])
    {
        d[e.ff] = d[x]^e.ss;
        dep[e.ff] = dep[x] + 1;
        dfs(e.ff, x);
    }
    eulend[x] = cureul;
}

void bbuild(int p, int l, int r)
{
    if(l == r)
    {
        int curl = 0;
        while(curl <= 30)
            roots[p] = new node(curl++, roots[p], nullptr);

        return ;
    }
    bbuild(2 * p, l, (l + r)/2);
    bbuild(2 * p + 1, (l + r)/2 + 1, r);
    roots[p] = new node(roots[2 * p]);
}
int jump(int a, int k)
{
    for(int i =0 ;i  < 20; i++)
        if((1 << i) & k)
            a=  sp[a][i];
}
int lca(int a, int b)
{
    if(dep[a] < dep[b])
        swap(a, b);
    a = jump(a, dep[a] - dep[b]);
    if(a == b)
        return a;

}
void solve()
{
    cin >> q;
    vector<pair<int,pii>>  queries;
    for(int i = 1; i <= q; i++)
    {
        string s; cin >> s;
        int x, y;
        cin >> x >> y;
        if(s== "Add")
        {
            adj[x].pb({++n, y});
            x = n;
        }
        queries.pb({(s == "Query"), {x, y}});
    }

    dfs(1, 0);

    while(k < n)
        k = (k << 1);
    //bbuild(1, 0, k - 1);
    pupd(0, 0);
   // cout << squery(1, 0, k - 1, eul[1], eulend[1], d[1]) << '\n';
    for(auto e: queries)
    {
        if(e.ff == 0)
        {
            //cout << e.ss.ff << ' ' << eul[e.ss.ff] << endl;
            update(roots[1], d[e.ss.ff], 30);
        }
        else
        {
            int a = e.ss.ff;
            int b = e.ss.ss;
           // cout << a << ' ' << b << endl;
            cout << query(roots[1], d[a]) << '\n';
        }
    }
}
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt--)
        solve();
}

Compilation message

klasika.cpp: In function 'int jump(int, int)':
klasika.cpp:140:1: warning: no return statement in function returning non-void [-Wreturn-type]
  140 | }
      | ^
klasika.cpp: In function 'void solve()':
klasika.cpp:184:17: warning: unused variable 'b' [-Wunused-variable]
  184 |             int b = e.ss.ss;
      |                 ^
klasika.cpp: In function 'int lca(int, int)':
klasika.cpp:149:1: warning: control reaches end of non-void function [-Wreturn-type]
  149 | }
      | ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 76572 KB Output is correct
2 Correct 271 ms 139156 KB Output is correct
3 Correct 327 ms 199732 KB Output is correct
4 Correct 367 ms 260696 KB Output is correct
5 Correct 193 ms 75032 KB Output is correct
6 Correct 250 ms 135948 KB Output is correct
7 Correct 333 ms 194876 KB Output is correct
8 Correct 403 ms 254168 KB Output is correct
9 Correct 186 ms 74812 KB Output is correct
10 Correct 257 ms 136692 KB Output is correct
11 Correct 306 ms 196672 KB Output is correct
12 Correct 346 ms 255696 KB Output is correct

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -