제출 #1349416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1349416		haru09	Klasika (COCI20_klasika)	C++20	33 / 110	989 ms	571760 KiB

klasika

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "task"

const int ar = 2e5 + 5;
const ll mod = 1e9 + 7;
int q, n = 1;
vector<int> ad[ar];
int d[ar], app[ar];
vector<pair<int, int>> Q[ar];
int sz[ar], timedfs = 0;
int in[ar];
int par[ar];
void dfs(int u)
{
    sz[u] = 1;
    for (int v : ad[u])
    {
        dfs(v);
        par[v] = u;
        sz[u] = sz[v] + 1;
    }
}
int curchain = 1;
int head[ar], chainid[ar];
void hld(int u)
{
    if (head[curchain] == 0)
    {
        head[curchain] = u;
    }
    in[u] = ++timedfs;
    chainid[u] = curchain;
    int _sz = 0;
    int bigc = 0;
    for (int v : ad[u])
    {
        if (sz[v] > _sz) _sz = sz[v], bigc = v;
    }
    if (bigc) hld(bigc);
    for (int v : ad[u])
    {
        if (v == bigc) continue;
        curchain++;
        hld(v);
    }
}
vector<pair<int, int>> on[ar], off[ar];
void get_segments(int u, int v)
{
    int root = u;
    while(u != 0)
    {
        int r = in[u];
        int l = in[head[chainid[u]]];
        //cout << l << ' ' << r << ' ' << root << ' ' << app[root] << '\n';
        on[l].push_back({v, app[root]});
        off[r].push_back({v, app[root]});
        u = par[head[chainid[u]]];
    }
}
struct Trie
{
    struct Node
    {
        int cnt;
        multiset<int> st;
        int child[2];
    } nodes[ar * 30];
    int cur = 0;
    Trie()
    {
        nodes[0].child[0] = nodes[0].child[1] = -1;
        nodes[0].cnt = 0;
    }
    int new_node()
    {
        ++cur;
        nodes[cur].child[0] = nodes[cur].child[1] = -1;
        nodes[cur].cnt = 0;
        return cur;
    }
    void add(int u, int v)
    {
        int p = 0;
        for (int i = 29; i >= 0; i--)
        {
            int c = (u >> i) & 1;
            if (nodes[p].child[c] == -1)
            {
                nodes[p].child[c] = new_node();
            }
            p = nodes[p].child[c];
            nodes[p].cnt++;
            nodes[p].st.insert(v);
        }
    }
    void del(int u, int v)
    {
        int p = 0;
        for (int i = 29; i >= 0; i--)
        {
            int c = (u >> i) & 1;
            p = nodes[p].child[c];
            nodes[p].cnt--;
            nodes[p].st.erase(nodes[p].st.find(v));
        }
    }
    int get(int u, int v)
    {
        int ans = 0;
        int p = 0;
        for (int i = 29; i >= 0; i--)
        {
            int c = (u >> i) & 1;
            if (nodes[p].child[c ^ 1] != -1 && nodes[nodes[p].child[c ^ 1]].cnt)
            {
                auto id = nodes[nodes[p].child[c ^ 1]].st.begin();
                if ((*id) <= v)
                {
                    ans += 1 << i;
                    p = nodes[p].child[c ^ 1];
                }
                else p = nodes[p].child[c];
            }
            else p = nodes[p].child[c];
        }
        return ans;
    }
} trie;
int ord[ar];
int ans[ar];
bool isquery[ar];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        string s;
        int x, y;
        cin >> s >> x >> y;
        if (s == "Add")
        {
            ad[x].push_back(++n);
            d[n] = d[x] ^ y;
            app[n] = i;
        }
        else
        {
            isquery[i] = true;
            Q[y].push_back({x, i});
        }
    }
    dfs(1);
    hld(1);
    for (int i = 1; i <= n; i++)
    {
        get_segments(i, d[i]);
        ord[i] = i;
    }
    sort(ord + 1, ord + n + 1, [&](int x, int y)
    {
        return in[x] < in[y];
    });
    for (int i = 1; i <= n; i++)
    {
        int u = ord[i];
        for (auto [v, t] : on[i]) trie.add(v, t);
        for (auto [v, t] : Q[u]) ans[t] = trie.get(d[v], t);
        for (auto [v, t] : off[i]) trie.del(v, t);
    }
    for (int i = 1; i <= q; i++)
    {
        if (isquery[i]) cout << ans[i] << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

klasika.cpp: In function 'int main()':
klasika.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44