oj.uz

Submission #1114280

# Submission time Handle Problem Language Result Execution time Memory
1114280 2024-11-18T13:24:16 Z ljtunas Klasika (COCI20_klasika) C++14
110 / 110
 2490 ms 442076 KB 
#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define fi first
#define se second
#define Rep(i, n)  for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define all(h) h.begin(), h.end()
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 2e5  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

// (x, y) -> (u, v) = Ckn(u - x, x + y - u - v);
// Ckn(k, a) * Ckn(k, b) = C(a, a + b);  (k : 1 -> min(a, b))

void fixmod(int &val) {
    if (val < 0) val += MOD*MOD;
    val %= MOD;
}
int n = 1, q, f[MAXN], num[MAXN], tail[MAXN];
vii g[MAXN];

struct Query{
	int x, y, type;
}; vector<Query> Q;

void dfs_init(int u, int par, int val) {
	static int time_dfs = 0;
	num[u] = ++time_dfs;
	f[u] = val;
	Forv(tmp, g[u]) {
		if (tmp.fi == par) continue;
		dfs_init(tmp.fi, u, val ^ tmp.se);
	}
	tail[u] = time_dfs;
}

struct node {
	set<int> s;
    node *child[2];
    node() {
        child[0] = child[1] = nullptr;
    }
};

struct Trie{
    node *root = new node();
    void add(int x, int id) {
        node *r = root;
        Ford(bit, 30, -1) {
        	r -> s.insert(id);
        	if (bit < 0) break;
            int k = Bit(x, bit);
            if (r -> child[k] == nullptr)
                r -> child[k] = new node;
            r = r -> child[k];
        }
    }
    int get(int x, int in, int en) {
    	node *r = root;
    	int res = 0;
    	Ford(bit, 30, -1) {
    		if (bit < 0) break;
    		int k = Bit(x, bit);
    		if (r->child[!k]==nullptr||r->child[!k]->s.lower_bound(in)==r->child[!k]->s.upper_bound(en)){
    			r = r->child[k];
    		} else {
    			res += (1<<bit);
    			r=r->child[!k];
    		}
    	}
    	return res;
    }
} Trie;

void Progess() {
	cin >> q;
	while (q--) {
		int x, y;
		string s; cin >> s >> x >> y;
		if (s == "Add") {
			++n;
			Q.emplace_back(Query{n, y, 1});
			g[x].emplace_back(ii{n, y});
			g[n].emplace_back(ii{x, y});
		} else {
			Q.emplace_back(Query{x, y, 0});
		}
	}
	dfs_init(1, 0, 0);
	Trie.add(0, 1);
	Forv(tmp, Q) {
		if (tmp.type == 1) {
			Trie.add(f[tmp.x], num[tmp.x]);
		} else {
			cout << Trie.get(f[tmp.x], num[tmp.y], tail[tmp.y]) << '\n';
		}
	}
}

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

    #define task "main"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }//_______________________________
    Progess();
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return (0 ^ 0);
}

Compilation message

klasika.cpp:32:23: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   32 | const int   oo = 1e18 + 1;
      |                  ~~~~~^~~
klasika.cpp: In function 'void fixmod(int&)':
klasika.cpp:49:28: warning: integer overflow in expression of type 'int' results in '-371520463' [-Woverflow]
   49 |     if (val < 0) val += MOD*MOD;
      |                         ~~~^~~~
klasika.cpp: In function 'int main()':
klasika.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 3 ms 6992 KB Output is correct
3 Correct 3 ms 6992 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 2 ms 6904 KB Output is correct
6 Correct 2 ms 7164 KB Output is correct
7 Correct 3 ms 6992 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 7048 KB Output is correct
11 Correct 3 ms 6992 KB Output is correct
12 Correct 3 ms 7312 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 3 ms 6992 KB Output is correct
3 Correct 3 ms 6992 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 2 ms 6904 KB Output is correct
6 Correct 2 ms 7164 KB Output is correct
7 Correct 3 ms 6992 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 7048 KB Output is correct
11 Correct 3 ms 6992 KB Output is correct
12 Correct 3 ms 7312 KB Output is correct
13 Correct 6 ms 8016 KB Output is correct
14 Correct 9 ms 9552 KB Output is correct
15 Correct 8 ms 10832 KB Output is correct
16 Correct 9 ms 11856 KB Output is correct
17 Correct 5 ms 8016 KB Output is correct
18 Correct 7 ms 9212 KB Output is correct
19 Correct 8 ms 10576 KB Output is correct
20 Correct 9 ms 11856 KB Output is correct
21 Correct 5 ms 8016 KB Output is correct
22 Correct 8 ms 9296 KB Output is correct
23 Correct 8 ms 10576 KB Output is correct
24 Correct 8 ms 11856 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 126604 KB Output is correct
2 Correct 1053 ms 234324 KB Output is correct
3 Correct 1535 ms 337672 KB Output is correct
4 Correct 1776 ms 441712 KB Output is correct
5 Correct 600 ms 124656 KB Output is correct
6 Correct 1082 ms 230316 KB Output is correct
7 Correct 1527 ms 331688 KB Output is correct
8 Correct 2047 ms 433132 KB Output is correct
9 Correct 643 ms 124232 KB Output is correct
10 Correct 965 ms 231100 KB Output is correct
11 Correct 1319 ms 334068 KB Output is correct
12 Correct 1687 ms 435188 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 3 ms 6992 KB Output is correct
3 Correct 3 ms 6992 KB Output is correct
4 Correct 2 ms 7248 KB Output is correct
5 Correct 2 ms 6904 KB Output is correct
6 Correct 2 ms 7164 KB Output is correct
7 Correct 3 ms 6992 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 7048 KB Output is correct
11 Correct 3 ms 6992 KB Output is correct
12 Correct 3 ms 7312 KB Output is correct
13 Correct 6 ms 8016 KB Output is correct
14 Correct 9 ms 9552 KB Output is correct
15 Correct 8 ms 10832 KB Output is correct
16 Correct 9 ms 11856 KB Output is correct
17 Correct 5 ms 8016 KB Output is correct
18 Correct 7 ms 9212 KB Output is correct
19 Correct 8 ms 10576 KB Output is correct
20 Correct 9 ms 11856 KB Output is correct
21 Correct 5 ms 8016 KB Output is correct
22 Correct 8 ms 9296 KB Output is correct
23 Correct 8 ms 10576 KB Output is correct
24 Correct 8 ms 11856 KB Output is correct
25 Correct 653 ms 126604 KB Output is correct
26 Correct 1053 ms 234324 KB Output is correct
27 Correct 1535 ms 337672 KB Output is correct
28 Correct 1776 ms 441712 KB Output is correct
29 Correct 600 ms 124656 KB Output is correct
30 Correct 1082 ms 230316 KB Output is correct
31 Correct 1527 ms 331688 KB Output is correct
32 Correct 2047 ms 433132 KB Output is correct
33 Correct 643 ms 124232 KB Output is correct
34 Correct 965 ms 231100 KB Output is correct
35 Correct 1319 ms 334068 KB Output is correct
36 Correct 1687 ms 435188 KB Output is correct
37 Correct 1044 ms 127512 KB Output is correct
38 Correct 1667 ms 234440 KB Output is correct
39 Correct 2117 ms 339912 KB Output is correct
40 Correct 2230 ms 442076 KB Output is correct
41 Correct 1173 ms 125172 KB Output is correct
42 Correct 1510 ms 230200 KB Output is correct
43 Correct 2263 ms 331912 KB Output is correct
44 Correct 2490 ms 432628 KB Output is correct
45 Correct 1328 ms 124656 KB Output is correct
46 Correct 1827 ms 231084 KB Output is correct
47 Correct 2067 ms 332644 KB Output is correct
48 Correct 2142 ms 435196 KB Output is correct