Submission #671620

#	Time	Username	Problem	Language	Result	Execution time	Memory
671620		US3RN4M3	Inside information (BOI21_servers)	C++17	32.50 / 100	1437 ms	524288 KiB

servers

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct ps {
	int size;
	int cnt;
	bool need_copy;
	ps * l;
	ps * r;
	ps() {}
	ps(int sz) {
		need_copy = false;
		size = sz;
		cnt = 0;
		if(size > 1) {
			l = new ps(size/2);
			r = new ps((size+1)/2);
		}
	}
	ps(ps & oth) {
		*this = oth;
		need_copy = true;
	}
	void push() {
		if(size == 1) return;
		if(need_copy) {
			need_copy = false;
			l = new ps(*l);
			r = new ps(*r);
		}
	}
	void ins(int i) {
		push();
		if(size == 1) {
			cnt = 1;
		} else {
			if(i < l->size) l->ins(i);
			else r->ins(i - l->size);
			cnt = l->cnt + r->cnt;
		}
	}
	int check(int i) {
		if(size == 1) return cnt;
		if(i < l->size) return l->check(i);
		else return r->check(i - l->size);
	}
	void vectorize(vector<int> & v, int pos = 0) {
		if(!cnt) return;
		if(size == 1) {
			v.push_back(pos);
		} else {
			l->vectorize(v, pos);
			r->vectorize(v, pos + l->size);
		}
	}
};
const int mx = 200005;
ps trees[mx];
void share(int a, int b) {
	if(trees[a].cnt > trees[b].cnt) swap(a, b);
	vector<int> a_elems;
	trees[a].vectorize(a_elems);
	for(int i : a_elems) trees[b].ins(i);
	trees[a] = ps(trees[b]);
	trees[b].need_copy = true;
}
void query(int a, int d) {
	if(trees[a].check(d)) cout << "yes" << endl;
	else cout << "no" << endl;
}
void count(int d) {
	cout << 1 << endl;
}
main() {
	int n, k; cin >> n >> k;
	ps emp(n + 1);
	for(int i = 1; i <= n; i++) {
		trees[i] = ps(emp);
		trees[i].ins(i);
		trees[i].need_copy = true;
	}
	for(int i = 0; i < n + k - 1; i++) {
		char opp; cin >> opp;
		if(opp == 'S') {
			int a, b;
			cin >> a >> b;
			share(a, b);
		} else if(opp == 'Q') {
			int a, d;
			cin >> a >> d;
			query(a, d);
		} else {
			for(int j = 1; j <= n; j++) {
				vector<int> tmp;
				trees[j].vectorize(tmp);
				for(int k : tmp) cout << k << " ";
				cout << endl;
			}
		}
	}
}

Compilation message (stderr)

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

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5