oj.uz

Submission #737615

# Submission time Handle Problem Language Result Execution time Memory
737615 2023-05-07T12:34:30 Z Sam_a17 Klasika (COCI20_klasika) C++17
110 / 110
 2698 ms 507444 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

int ka() {
	int x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 1;
vector<int> adj[N];
int q, tin[N], tout[N], timer;
int dp[N];

const int M = N * 12;
int cnt, t[M][2];
set<int> stik[M][2];

void init() {
  for(int i = 0; i < M; i++) {
    t[i][0] = t[i][1] = -1;
  }
}

void upd(int x, int tt) {
  int st = 0;
  for(int i = 30; i >= 0; i--) {
    bool flag = (x >> i) & 1;
    if(t[st][flag] == -1) {
      t[st][flag] = ++cnt;
    }
    stik[st][flag].insert(tt);
    st = t[st][flag];
  }
}

int qry(int x, int star, int en) {
  int answ = 0, st = 0;
  for(int i = 30; i >= 0; i--) {
    bool flag = (x >> i) & 1;
    auto bit = stik[st][!flag].lower_bound(star);
    if(!stik[st][!flag].empty() 
      && bit != stik[st][!flag].end() && *bit >= star && *bit <= en) {
      st = t[st][!flag];
      answ |= (1 << i);
    } else {
      st = t[st][flag];
    }
  }
  return answ;
}

struct query {
  string s;
  long long x, y;
};

vector<query> queries;

void dfs(int node) {
  tin[node] = timer++;
  for(auto i: adj[node]) {
    dfs(i);
  }
  tout[node] = timer - 1;
}

void solve_() {
  cin >> q;
  // dp[1] = 0;

  int it = 2;
  for(int i = 1; i <= q; i++) {
    string s; cin >> s;
    int x, y; cin >> x >> y;
    if(s[0] == 'A') {
      adj[x].push_back(it);
      it++;
    }
    queries.push_back({s, x, y});
  }

  dfs(1);

  init();
  upd(0, tin[1]);
  it = 2;
  for(auto i: queries) {
    string s = i.s;
    long long x = i.x, y = i.y;

    if(s[0] == 'A') {
      dp[it] = dp[x] ^ y;
      upd(dp[it], tin[it]);
      it++;
    } else {
      cout << qry(dp[x], tin[y], tout[y]) << '\n';
    } 
  }
} 
 
int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

klasika.cpp: In function 'void setIO(std::string)':
klasika.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 249292 KB Output is correct
2 Correct 108 ms 249376 KB Output is correct
3 Correct 118 ms 249324 KB Output is correct
4 Correct 107 ms 249416 KB Output is correct
5 Correct 111 ms 249256 KB Output is correct
6 Correct 107 ms 249392 KB Output is correct
7 Correct 107 ms 249388 KB Output is correct
8 Correct 107 ms 249436 KB Output is correct
9 Correct 108 ms 249240 KB Output is correct
10 Correct 110 ms 249400 KB Output is correct
11 Correct 107 ms 249520 KB Output is correct
12 Correct 108 ms 249596 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 249292 KB Output is correct
2 Correct 108 ms 249376 KB Output is correct
3 Correct 118 ms 249324 KB Output is correct
4 Correct 107 ms 249416 KB Output is correct
5 Correct 111 ms 249256 KB Output is correct
6 Correct 107 ms 249392 KB Output is correct
7 Correct 107 ms 249388 KB Output is correct
8 Correct 107 ms 249436 KB Output is correct
9 Correct 108 ms 249240 KB Output is correct
10 Correct 110 ms 249400 KB Output is correct
11 Correct 107 ms 249520 KB Output is correct
12 Correct 108 ms 249596 KB Output is correct
13 Correct 112 ms 249932 KB Output is correct
14 Correct 115 ms 250644 KB Output is correct
15 Correct 111 ms 251312 KB Output is correct
16 Correct 112 ms 251720 KB Output is correct
17 Correct 109 ms 249940 KB Output is correct
18 Correct 110 ms 250468 KB Output is correct
19 Correct 112 ms 251188 KB Output is correct
20 Correct 127 ms 251856 KB Output is correct
21 Correct 157 ms 249936 KB Output is correct
22 Correct 110 ms 250572 KB Output is correct
23 Correct 114 ms 251196 KB Output is correct
24 Correct 118 ms 251676 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 324068 KB Output is correct
2 Correct 1233 ms 385576 KB Output is correct
3 Correct 1645 ms 445840 KB Output is correct
4 Correct 2130 ms 507392 KB Output is correct
5 Correct 782 ms 322408 KB Output is correct
6 Correct 1306 ms 382472 KB Output is correct
7 Correct 1826 ms 440828 KB Output is correct
8 Correct 2372 ms 500156 KB Output is correct
9 Correct 788 ms 322392 KB Output is correct
10 Correct 1249 ms 383012 KB Output is correct
11 Correct 1751 ms 442536 KB Output is correct
12 Correct 2198 ms 501928 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 249292 KB Output is correct
2 Correct 108 ms 249376 KB Output is correct
3 Correct 118 ms 249324 KB Output is correct
4 Correct 107 ms 249416 KB Output is correct
5 Correct 111 ms 249256 KB Output is correct
6 Correct 107 ms 249392 KB Output is correct
7 Correct 107 ms 249388 KB Output is correct
8 Correct 107 ms 249436 KB Output is correct
9 Correct 108 ms 249240 KB Output is correct
10 Correct 110 ms 249400 KB Output is correct
11 Correct 107 ms 249520 KB Output is correct
12 Correct 108 ms 249596 KB Output is correct
13 Correct 112 ms 249932 KB Output is correct
14 Correct 115 ms 250644 KB Output is correct
15 Correct 111 ms 251312 KB Output is correct
16 Correct 112 ms 251720 KB Output is correct
17 Correct 109 ms 249940 KB Output is correct
18 Correct 110 ms 250468 KB Output is correct
19 Correct 112 ms 251188 KB Output is correct
20 Correct 127 ms 251856 KB Output is correct
21 Correct 157 ms 249936 KB Output is correct
22 Correct 110 ms 250572 KB Output is correct
23 Correct 114 ms 251196 KB Output is correct
24 Correct 118 ms 251676 KB Output is correct
25 Correct 726 ms 324068 KB Output is correct
26 Correct 1233 ms 385576 KB Output is correct
27 Correct 1645 ms 445840 KB Output is correct
28 Correct 2130 ms 507392 KB Output is correct
29 Correct 782 ms 322408 KB Output is correct
30 Correct 1306 ms 382472 KB Output is correct
31 Correct 1826 ms 440828 KB Output is correct
32 Correct 2372 ms 500156 KB Output is correct
33 Correct 788 ms 322392 KB Output is correct
34 Correct 1249 ms 383012 KB Output is correct
35 Correct 1751 ms 442536 KB Output is correct
36 Correct 2198 ms 501928 KB Output is correct
37 Correct 1250 ms 324984 KB Output is correct
38 Correct 1759 ms 385700 KB Output is correct
39 Correct 2109 ms 447544 KB Output is correct
40 Correct 2414 ms 507444 KB Output is correct
41 Correct 1371 ms 322960 KB Output is correct
42 Correct 1911 ms 382176 KB Output is correct
43 Correct 2334 ms 441160 KB Output is correct
44 Correct 2698 ms 499828 KB Output is correct
45 Correct 1450 ms 322696 KB Output is correct
46 Correct 1842 ms 383180 KB Output is correct
47 Correct 2171 ms 442020 KB Output is correct
48 Correct 2501 ms 501944 KB Output is correct