oj.uz

Submission #513512

# Submission time Handle Problem Language Result Execution time Memory
513512 2022-01-17T07:39:55 Z Killer2501 Klasika (COCI20_klasika) C++14
110 / 110
 2940 ms 483148 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = (1<<17);
const ll inf = 1e15;
const ll mod = 1e15+7;
int n, t, k, m, d[N], in[N], out[N];
int ans, tong, a[N], b[N];
string s[N];
struct node
{
    int x[2];
    set<int> vi;
    node(){}
    node( int _x, int _y)
    {
        x[0] = _x;
        x[1] = _y;
    }

};
vector<node> q;
vector<int>  adj[N], kq;
void add(int x, int y)
{
    for(int i = 0, j = 30; j >= 0; j --)
    {
        int t = (x >> j & 1);
        if(q[i].x[t] == 0)
        {
            q[i].x[t] = q.size();
            q.pb(node(0, 0));
        }
        i = q[i].x[t];
        q[i].vi.insert(y);
    }
}
int get(int x, int l, int r)
{
    int total = 0;
    for(int i = 0, j = 30; j >= 0; j --)
    {
        int t = (x >> j & 1);
        int nxt = q[i].x[t^1];
        auto it = q[nxt].vi.lower_bound(l);
        if(it != q[nxt].vi.end() && (*it) <= r)
        {
            i = nxt;
            total += (1<<j);
        }
        else i = q[i].x[t];
    }
    return total;
}
void dfs(int u)
{
    in[u] = ++k;
    for(int v: adj[u])dfs(v);
    out[u] = k;
}
void sol()
{
    cin >> m;
    n = 1;
    for(int i = 1; i <= m; i ++)
    {
        cin >> s[i] >> a[i] >> b[i];
        if(s[i] == "Add")
        {
            ++n;
            adj[a[i]].pb(n);
            d[n] = d[a[i]] ^ b[i];
            a[i] = n;
        }
    }
    dfs(1);
    q.pb(node(0, 0));
    add(d[1], in[1]);
    for(int i = 1; i <= m; i ++)
    {
        if(s[i] == "Add")
        {
            add(d[a[i]], in[a[i]]);
        }
        else cout << get(d[a[i]], in[b[i]], out[b[i]]) << '\n';
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16972 KB Output is correct
2 Correct 9 ms 16916 KB Output is correct
3 Correct 10 ms 17148 KB Output is correct
4 Correct 10 ms 17228 KB Output is correct
5 Correct 10 ms 16808 KB Output is correct
6 Correct 10 ms 16972 KB Output is correct
7 Correct 9 ms 17144 KB Output is correct
8 Correct 9 ms 17148 KB Output is correct
9 Correct 9 ms 16972 KB Output is correct
10 Correct 9 ms 17156 KB Output is correct
11 Correct 9 ms 17100 KB Output is correct
12 Correct 9 ms 17228 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16972 KB Output is correct
2 Correct 9 ms 16916 KB Output is correct
3 Correct 10 ms 17148 KB Output is correct
4 Correct 10 ms 17228 KB Output is correct
5 Correct 10 ms 16808 KB Output is correct
6 Correct 10 ms 16972 KB Output is correct
7 Correct 9 ms 17144 KB Output is correct
8 Correct 9 ms 17148 KB Output is correct
9 Correct 9 ms 16972 KB Output is correct
10 Correct 9 ms 17156 KB Output is correct
11 Correct 9 ms 17100 KB Output is correct
12 Correct 9 ms 17228 KB Output is correct
13 Correct 11 ms 18280 KB Output is correct
14 Correct 13 ms 19812 KB Output is correct
15 Correct 15 ms 20064 KB Output is correct
16 Correct 18 ms 22816 KB Output is correct
17 Correct 11 ms 18204 KB Output is correct
18 Correct 13 ms 19772 KB Output is correct
19 Correct 15 ms 20088 KB Output is correct
20 Correct 16 ms 20988 KB Output is correct
21 Correct 12 ms 18176 KB Output is correct
22 Correct 14 ms 19724 KB Output is correct
23 Correct 17 ms 20000 KB Output is correct
24 Correct 16 ms 20896 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 127668 KB Output is correct
2 Correct 1158 ms 244704 KB Output is correct
3 Correct 1660 ms 298044 KB Output is correct
4 Correct 2238 ms 482872 KB Output is correct
5 Correct 702 ms 128492 KB Output is correct
6 Correct 1365 ms 241432 KB Output is correct
7 Correct 1842 ms 293968 KB Output is correct
8 Correct 2543 ms 476156 KB Output is correct
9 Correct 695 ms 128848 KB Output is correct
10 Correct 1239 ms 242080 KB Output is correct
11 Correct 1697 ms 296004 KB Output is correct
12 Correct 2353 ms 477528 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16972 KB Output is correct
2 Correct 9 ms 16916 KB Output is correct
3 Correct 10 ms 17148 KB Output is correct
4 Correct 10 ms 17228 KB Output is correct
5 Correct 10 ms 16808 KB Output is correct
6 Correct 10 ms 16972 KB Output is correct
7 Correct 9 ms 17144 KB Output is correct
8 Correct 9 ms 17148 KB Output is correct
9 Correct 9 ms 16972 KB Output is correct
10 Correct 9 ms 17156 KB Output is correct
11 Correct 9 ms 17100 KB Output is correct
12 Correct 9 ms 17228 KB Output is correct
13 Correct 11 ms 18280 KB Output is correct
14 Correct 13 ms 19812 KB Output is correct
15 Correct 15 ms 20064 KB Output is correct
16 Correct 18 ms 22816 KB Output is correct
17 Correct 11 ms 18204 KB Output is correct
18 Correct 13 ms 19772 KB Output is correct
19 Correct 15 ms 20088 KB Output is correct
20 Correct 16 ms 20988 KB Output is correct
21 Correct 12 ms 18176 KB Output is correct
22 Correct 14 ms 19724 KB Output is correct
23 Correct 17 ms 20000 KB Output is correct
24 Correct 16 ms 20896 KB Output is correct
25 Correct 633 ms 127668 KB Output is correct
26 Correct 1158 ms 244704 KB Output is correct
27 Correct 1660 ms 298044 KB Output is correct
28 Correct 2238 ms 482872 KB Output is correct
29 Correct 702 ms 128492 KB Output is correct
30 Correct 1365 ms 241432 KB Output is correct
31 Correct 1842 ms 293968 KB Output is correct
32 Correct 2543 ms 476156 KB Output is correct
33 Correct 695 ms 128848 KB Output is correct
34 Correct 1239 ms 242080 KB Output is correct
35 Correct 1697 ms 296004 KB Output is correct
36 Correct 2353 ms 477528 KB Output is correct
37 Correct 1211 ms 130704 KB Output is correct
38 Correct 1768 ms 245100 KB Output is correct
39 Correct 2185 ms 300420 KB Output is correct
40 Correct 2518 ms 483148 KB Output is correct
41 Correct 1310 ms 128960 KB Output is correct
42 Correct 1897 ms 241744 KB Output is correct
43 Correct 2356 ms 294100 KB Output is correct
44 Correct 2940 ms 476424 KB Output is correct
45 Correct 1497 ms 129308 KB Output is correct
46 Correct 2045 ms 242500 KB Output is correct
47 Correct 2190 ms 294932 KB Output is correct
48 Correct 2664 ms 477852 KB Output is correct