Submission #1119028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119028		vjudge1	Klasika (COCI20_klasika)	C++17	110 / 110	3487 ms	524288 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

#define TASK ""
#define int long long
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

mt19937 rng(time(0));

const int N = (int)2e5 + 7;
int q;
vector<int> adj[N];
int n = 1;
int f[N];

void Read()
{
    cin >> q;
}

namespace Subtask4
{
    const int LOG = 31;
    struct Node
    {
        int c[2];
        set<int> s;
        Node() {
            c[0] = 0;
            c[1] = 0;
        }
    };
    vector<Node> Trie(1);

    int in[N], out[N], timeVis = 0;
    array<int, 3> query[N];

    void Insert(int mask, int p)
    {
        int id = 0;
        FORD(i, LOG, 0)
        {
            int val = mask >> i & 1;
//            cout << id << ' ';
            if(!Trie[id].c[val])
            {
                Trie[id].c[val] = Trie.size();
                Trie.push_back(Node());
            }
            id = Trie[id].c[val];
            Trie[id].s.insert(in[p]);
        }
//        cout << '\n';
    }

    bool InTree(set<int>& s, int L, int R)
    {
        auto it = s.lower_bound(L);
        return (it != s.end() && *it <= R);
    }

    int Ask(int mask, int p)
    {
        int id = 0, res = 0;
        FORD(i, LOG, 0)
        {
//            cout << id << ' ';
            int val = mask >> i & 1;
            val ^= 1;
            if(Trie[id].c[val] && InTree(Trie[Trie[id].c[val]].s, in[p], out[p]))
            {
                id = Trie[id].c[val];
                res += (1 << i);
            }
            else
                id = Trie[id].c[val ^ 1];
        }
//        cout << '\n';
        return res;
    }

    using ii = pair<int, int>;
    vector<ii> G[N];

    void DFS(int u, int p = 0)
    {
        in[u] = ++timeVis;
        for(auto [v, w] : G[u])
        {
            if(v == p)
                continue;
            f[v] = f[u] ^ w;
            DFS(v, u);
        }
        out[u] = timeVis;
    }

    void Solve()
    {
        REP(i, q)
        {
            string type;
            int a, b;
            cin >> type >> a >> b;
            if(type[0] == 'A')
            {
                ++n;
                query[i] = {1, n, 0};
                G[a].push_back({n, b});
                G[n].push_back({a, b});
            }
            else
                query[i] = {2, a, b};
        }
        DFS(1);
        Insert(0, 1);
        REP(i, q)
        {
            auto [t, u, v] = query[i];
            if(t == 1)
                Insert(f[u], u);
            else
                cout << Ask(f[u], v) << '\n';
        }
    }

}

void Solve()
{
//    if(Subtask2::Check()) return Subtask2::Solve();
    return Subtask4::Solve();
}

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    Read();
    Solve();

    return 0;
}

/*
5
Add 1 5
Add 2 7
Add 1 5
Add 4 8
Query 3 1
*/

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:145:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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