답안 #633397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633397	2022-08-22T10:36:20 Z	IWTIM	Klasika (COCI20_klasika)	C++14	110 / 110	2810 ms	435456 KB

klasika

# include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 998244353;
const int MX = 2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
 
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
const int N = 3e5 + 5;
int t,n,in[N], trie[10*N][3], out[N],tin,rt[N],qa[N],qb[N],ty[N],sz;
int q;
set <int> s[10*N];
vector <pii> v[N];
void dfs(int a, int p, int c) {
	tin++;
	if (p == 0) rt[a] = 0;
	else rt[a] = rt[p] ^ c;
	in[a] = tin;
	for (auto to : v[a]) {
		if (to.f == p) continue;
		dfs(to.f,a,to.s);
	}
	out[a] = tin;
}
void insert(int val, int in) {
	int cur = 0;
	s[cur].insert(in);
	for (int i = 30; i >= 0; i--) {
		int c = 0;
		if ((1<<i)&val) c = 1;
		if (!trie[cur][c]) trie[cur][c] = ++sz;
		cur = trie[cur][c];
		s[cur].insert(in);
	}
}
int get(int val, int in, int out) {
	int cur = 0, ans = 0;
	for (int i = 30; i >= 0; i--) {
		int c = 0;
		if (!((1<<i)&val)) c = 1;
		int x = trie[cur][c];
		if (x && s[x].lower_bound(in) != s[x].end() && *s[x].lower_bound(in) <= out) cur = x, ans ^= (1<<i);
		else cur = trie[cur][c ^ 1];  
	}
	return ans;
}
main() {
//   std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>q;
    int n = 1;
    for (int i = 1; i <= q; i++) {
    	string s;
		cin>>s;
		if (s[0] == 'A') ty[i] = 0;
		else ty[i] = 1;
		if (!ty[i]) {
			int x, y;
			n++;
			cin>>x>>y;
			qa[i] = n; qb[i] = y;
			v[x].pb({n,y});
			v[n].pb({x,y});
		}
		else {
			cin>>qa[i]>>qb[i];
		}
	}
	dfs(1,0,0);
	for (int i = 1; i <= n; i++) {
		//cout<<i<<" "<<in[i]<<"--->"<<out[i]<<"   "<<rt[i]<<"\n";
	}
	insert(0,1);
	for (int i = 1; i <= q; i++) {
		if (!ty[i]) {
			int x = qa[i];
			insert(rt[x], in[x]);
		} else {
			cout<<get(rt[qa[i]], in[qb[i]], out[qb[i]])<<"\n";
		}
	}
}

Compilation message

klasika.cpp:219:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  219 | main() {
      | ^~~~

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	148380 KB	Output is correct
2	Correct	65 ms	148300 KB	Output is correct
3	Correct	71 ms	148440 KB	Output is correct
4	Correct	65 ms	148556 KB	Output is correct
5	Correct	70 ms	148276 KB	Output is correct
6	Correct	67 ms	148324 KB	Output is correct
7	Correct	65 ms	148484 KB	Output is correct
8	Correct	65 ms	148532 KB	Output is correct
9	Correct	66 ms	148340 KB	Output is correct
10	Correct	66 ms	148380 KB	Output is correct
11	Correct	67 ms	148480 KB	Output is correct
12	Correct	66 ms	148680 KB	Output is correct

Subtask #2

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	148380 KB	Output is correct
2	Correct	65 ms	148300 KB	Output is correct
3	Correct	71 ms	148440 KB	Output is correct
4	Correct	65 ms	148556 KB	Output is correct
5	Correct	70 ms	148276 KB	Output is correct
6	Correct	67 ms	148324 KB	Output is correct
7	Correct	65 ms	148484 KB	Output is correct
8	Correct	65 ms	148532 KB	Output is correct
9	Correct	66 ms	148340 KB	Output is correct
10	Correct	66 ms	148380 KB	Output is correct
11	Correct	67 ms	148480 KB	Output is correct
12	Correct	66 ms	148680 KB	Output is correct
13	Correct	68 ms	149028 KB	Output is correct
14	Correct	70 ms	149836 KB	Output is correct
15	Correct	71 ms	150600 KB	Output is correct
16	Correct	72 ms	151244 KB	Output is correct
17	Correct	69 ms	149028 KB	Output is correct
18	Correct	78 ms	149660 KB	Output is correct
19	Correct	86 ms	150520 KB	Output is correct
20	Correct	72 ms	151128 KB	Output is correct
21	Correct	69 ms	149068 KB	Output is correct
22	Correct	74 ms	149708 KB	Output is correct
23	Correct	84 ms	150448 KB	Output is correct
24	Correct	83 ms	151176 KB	Output is correct

Subtask #3

33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	886 ms	223072 KB	Output is correct
2	Correct	1331 ms	296584 KB	Output is correct
3	Correct	1884 ms	365216 KB	Output is correct
4	Correct	2480 ms	435120 KB	Output is correct
5	Correct	976 ms	224452 KB	Output is correct
6	Correct	1437 ms	293488 KB	Output is correct
7	Correct	2061 ms	361012 KB	Output is correct
8	Correct	2661 ms	429080 KB	Output is correct
9	Correct	840 ms	224356 KB	Output is correct
10	Correct	1415 ms	294140 KB	Output is correct
11	Correct	1862 ms	362544 KB	Output is correct
12	Correct	2386 ms	430468 KB	Output is correct

Subtask #4

44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	148380 KB	Output is correct
2	Correct	65 ms	148300 KB	Output is correct
3	Correct	71 ms	148440 KB	Output is correct
4	Correct	65 ms	148556 KB	Output is correct
5	Correct	70 ms	148276 KB	Output is correct
6	Correct	67 ms	148324 KB	Output is correct
7	Correct	65 ms	148484 KB	Output is correct
8	Correct	65 ms	148532 KB	Output is correct
9	Correct	66 ms	148340 KB	Output is correct
10	Correct	66 ms	148380 KB	Output is correct
11	Correct	67 ms	148480 KB	Output is correct
12	Correct	66 ms	148680 KB	Output is correct
13	Correct	68 ms	149028 KB	Output is correct
14	Correct	70 ms	149836 KB	Output is correct
15	Correct	71 ms	150600 KB	Output is correct
16	Correct	72 ms	151244 KB	Output is correct
17	Correct	69 ms	149028 KB	Output is correct
18	Correct	78 ms	149660 KB	Output is correct
19	Correct	86 ms	150520 KB	Output is correct
20	Correct	72 ms	151128 KB	Output is correct
21	Correct	69 ms	149068 KB	Output is correct
22	Correct	74 ms	149708 KB	Output is correct
23	Correct	84 ms	150448 KB	Output is correct
24	Correct	83 ms	151176 KB	Output is correct
25	Correct	886 ms	223072 KB	Output is correct
26	Correct	1331 ms	296584 KB	Output is correct
27	Correct	1884 ms	365216 KB	Output is correct
28	Correct	2480 ms	435120 KB	Output is correct
29	Correct	976 ms	224452 KB	Output is correct
30	Correct	1437 ms	293488 KB	Output is correct
31	Correct	2061 ms	361012 KB	Output is correct
32	Correct	2661 ms	429080 KB	Output is correct
33	Correct	840 ms	224356 KB	Output is correct
34	Correct	1415 ms	294140 KB	Output is correct
35	Correct	1862 ms	362544 KB	Output is correct
36	Correct	2386 ms	430468 KB	Output is correct
37	Correct	1508 ms	227000 KB	Output is correct
38	Correct	1981 ms	296556 KB	Output is correct
39	Correct	2363 ms	367128 KB	Output is correct
40	Correct	2653 ms	435456 KB	Output is correct
41	Correct	1538 ms	225012 KB	Output is correct
42	Correct	2017 ms	293620 KB	Output is correct
43	Correct	2454 ms	361168 KB	Output is correct
44	Correct	2798 ms	428640 KB	Output is correct
45	Correct	1599 ms	224704 KB	Output is correct
46	Correct	2118 ms	294328 KB	Output is correct
47	Correct	2483 ms	361732 KB	Output is correct
48	Correct	2810 ms	430380 KB	Output is correct