답안 #199563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199563 2020-02-02T03:47:13 Z SamAnd Klasika (COCI20_klasika) C++17
0 / 110
408 ms 75788 KB
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005;

int n, m;
pair<int, int> b[N];
vector<int> a[N];
int d[N];

int ti, tin[N], tout[N];
void dfs(int x)
{
    tin[x] = ++ti;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs(h);
    }
    tout[x] = ti;
}

int z[N * 4];
vector<vector<int> > t[N * 4];

void bil(int tl, int tr, int pos)
{
    t[pos].push_back({0, 0});
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
}

void ubd(int tl, int tr, int x, int y, int pos)
{
    int bpos = 0;
    for (int i = 30; i >= 0; --i)
    {
        int u;
        if (!(y & (1 << i)))
            u = 0;
        else
            u = 1;
        if (!t[pos][bpos][u])
        {
            t[pos][bpos][u] = ++z[pos];
            t[pos].push_back({0, 0});
        }
        bpos = t[pos][bpos][u];
    }
    return;
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
}

int qry(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
    {
        int bpos = 0;
        int ans = 0;
        if (z[pos] == 0)
            return ans;
        for (int i = 30; i >= 0; --i)
        {
            int u;
            if (!(y & (1 << i)))
                u = 0;
            else
                u = 1;
            if (t[pos][bpos][(u ^ 1)])
            {
                ans += (1 << i);
                bpos = t[pos][bpos][(u ^ 1)];
            }
            else
            {
                bpos = t[pos][bpos][u];
            }
        }
        return ans;
    }
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), y, pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1));
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &m);
    n = 1;
    for (int i = 1; i <= m; ++i)
    {
        char ty[10];
        scanf(" %s", ty);
        if (ty[0] == 'A')
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ++n;
            a[x].push_back(n);
            d[n] = (d[x] ^ y);
            b[i] = m_p(n, -1);
        }
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            b[i] = m_p(x, y);
        }
    }
    dfs(1);
    bil(1, n, 1);
    for (int i = 1; i <= m; ++i)
    {
        if (b[i].second == -1)
        {
            int x = b[i].first;
            ubd(1, n, tin[x], d[x], 1);
        }
        else
        {
            int x = b[i].first;
            int y = b[i].second;
            printf("%d\n", qry(1, n, tin[y], tout[y], d[x], 1));
        }
    }
    return 0;
}

Compilation message

klasika.cpp: In function 'void dfs(int)':
klasika.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
klasika.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", ty);
         ~~~~~^~~~~~~~~~~
klasika.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
klasika.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 408 ms 75788 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -