oj.uz

답안 #769561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769561 2023-06-29T19:13:20 Z MohamedAliSaidane Klasika (COCI20_klasika) C++14
33 / 110
 609 ms 524288 KB 
#include <bits/stdc++.h>

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);
    for(int j = 1; j < 20; j++)
        for(int i = 1; i <= n; i++)
            sp[i][j] = sp[sp[i][j - 1]][j - 1];
    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;
            pupd(eul[e.ss.ff], d[e.ss.ff]);
        }
        else
        {
            int a = e.ss.ff;
            int b = e.ss.ss;
           // cout << a << ' ' << b << endl;
            cout << squery(1, 0, k - 1, eul[b], eulend[b],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:139:1: warning: no return statement in function returning non-void [-Wreturn-type]
  139 | }
      | ^
klasika.cpp: In function 'int lca(int, int)':
klasika.cpp:148:1: warning: control reaches end of non-void function [-Wreturn-type]
  148 | }
      | ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 4 ms 6100 KB Output is correct
3 Correct 4 ms 6740 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 3 ms 5588 KB Output is correct
10 Correct 5 ms 6356 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 5 ms 7636 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 4 ms 6100 KB Output is correct
3 Correct 4 ms 6740 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 3 ms 5588 KB Output is correct
10 Correct 5 ms 6356 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 5 ms 7636 KB Output is correct
13 Correct 13 ms 12628 KB Output is correct
14 Correct 20 ms 21408 KB Output is correct
15 Correct 30 ms 31652 KB Output is correct
16 Correct 37 ms 39592 KB Output is correct
17 Correct 11 ms 12244 KB Output is correct
18 Correct 20 ms 20948 KB Output is correct
19 Correct 30 ms 31204 KB Output is correct
20 Correct 37 ms 39240 KB Output is correct
21 Correct 12 ms 12372 KB Output is correct
22 Correct 20 ms 21076 KB Output is correct
23 Correct 29 ms 31096 KB Output is correct
24 Correct 36 ms 39060 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 609 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 4 ms 6100 KB Output is correct
3 Correct 4 ms 6740 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 3 ms 5588 KB Output is correct
10 Correct 5 ms 6356 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 5 ms 7636 KB Output is correct
13 Correct 13 ms 12628 KB Output is correct
14 Correct 20 ms 21408 KB Output is correct
15 Correct 30 ms 31652 KB Output is correct
16 Correct 37 ms 39592 KB Output is correct
17 Correct 11 ms 12244 KB Output is correct
18 Correct 20 ms 20948 KB Output is correct
19 Correct 30 ms 31204 KB Output is correct
20 Correct 37 ms 39240 KB Output is correct
21 Correct 12 ms 12372 KB Output is correct
22 Correct 20 ms 21076 KB Output is correct
23 Correct 29 ms 31096 KB Output is correct
24 Correct 36 ms 39060 KB Output is correct
25 Runtime error 609 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -