Submission #1118712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118712		vjudge1	Klasika (COCI20_klasika)	C++17	0 / 110	106 ms	19956 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

#define TASK ""
#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 Subtask2
{
    bool Check()
    {
        return q <= 2000;
    }

    string type;
    int a, b;
    int ans = 0;

    void DFS(int u)
    {
        maximize(ans, f[a] ^ f[u]);
        for(int v : adj[u])
        {
            DFS(v);
        }
    }


    void Solve()
    {
        REP(i, q)
        {
            cin >> type >> a >> b;
            if(type[0] == 'A')
            {
                ++n;
                adj[a].push_back(n);
                f[n] = f[a] ^ b;
            }
            else
            {
                ans = 0;
                DFS(b);
                cout << ans << '\n';
            }
        }
    }
}

namespace Subtask3
{
    #define int long long
    int child[30 * N][2], sz = 0;
//    bool isEnd[100];

    string type;
    int a, b;

    void Ins(int mask)
    {
        int u = 0;
        FORD(i, 30, 0)
        {
            int val = mask >> i & 1;
            if(!child[u][val])
            {
                child[u][val] = ++sz;
                u = sz;
            }
            else
                u = child[u][val];
        }
    }

    int Ask(int mask)
    {
        int u = 0, res = 0;
        FORD(i, 30, 0)
        {
            int val = mask >> i & 1;
            val ^= 1;
            if(child[u][val])
            {
                u = child[u][val];
                res += (1 << i);
            }
            else
            {
                u = child[u][val ^ 1];
            }
        }
        return res;
    }

    void Solve()
    {
        REP(i, q)
        {
            cin >> type >> a >> b;
            if(type[0] == 'A')
            {
                ++n;
                f[n] = f[a] ^ b;
                Ins(f[n]);
            }
            else
            {
                cout << Ask(f[a]) << '\n';
            }
        }
    }
}

void Solve()
{
//    if(Subtask2::Check()) return Subtask2::Solve();
    return Subtask3::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;
}

/*
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
*/

Compilation message (stderr)

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

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