oj.uz

Submission #671620

# Submission time Handle Problem Language Result Execution time Memory
671620 2022-12-13T11:25:51 Z US3RN4M3 Inside information (BOI21_servers) C++17
32.5 / 100
 1437 ms 524288 KB 
#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

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 184 ms 1508 KB Output is correct
2 Correct 238 ms 13352 KB Output is correct
3 Correct 239 ms 12748 KB Output is correct
4 Correct 236 ms 13184 KB Output is correct
5 Correct 228 ms 11612 KB Output is correct
6 Correct 245 ms 11576 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 184 ms 1508 KB Output is correct
2 Correct 238 ms 13352 KB Output is correct
3 Correct 239 ms 12748 KB Output is correct
4 Correct 236 ms 13184 KB Output is correct
5 Correct 228 ms 11612 KB Output is correct
6 Correct 245 ms 11576 KB Output is correct
7 Incorrect 1031 ms 10292 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1512 KB Output is correct
2 Correct 939 ms 399692 KB Output is correct
3 Correct 914 ms 399704 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1512 KB Output is correct
2 Correct 939 ms 399692 KB Output is correct
3 Correct 914 ms 399704 KB Output is correct
4 Incorrect 1437 ms 23964 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1592 KB Output is correct
2 Correct 835 ms 404604 KB Output is correct
3 Correct 828 ms 404436 KB Output is correct
4 Correct 769 ms 400288 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1592 KB Output is correct
2 Correct 835 ms 404604 KB Output is correct
3 Correct 828 ms 404436 KB Output is correct
4 Correct 769 ms 400288 KB Output is correct
5 Incorrect 933 ms 6468 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 1512 KB Output is correct
2 Correct 933 ms 483056 KB Output is correct
3 Correct 961 ms 460828 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 1512 KB Output is correct
2 Correct 933 ms 483056 KB Output is correct
3 Correct 961 ms 460828 KB Output is correct
4 Incorrect 971 ms 7216 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1484 KB Output is correct
2 Correct 828 ms 404608 KB Output is correct
3 Correct 865 ms 404684 KB Output is correct
4 Correct 746 ms 400340 KB Output is correct
5 Correct 198 ms 1516 KB Output is correct
6 Correct 904 ms 483092 KB Output is correct
7 Correct 952 ms 460820 KB Output is correct
8 Correct 1012 ms 484360 KB Output is correct
9 Correct 1016 ms 484136 KB Output is correct
10 Correct 1042 ms 492940 KB Output is correct
11 Correct 1067 ms 493492 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1484 KB Output is correct
2 Correct 828 ms 404608 KB Output is correct
3 Correct 865 ms 404684 KB Output is correct
4 Correct 746 ms 400340 KB Output is correct
5 Correct 198 ms 1516 KB Output is correct
6 Correct 904 ms 483092 KB Output is correct
7 Correct 952 ms 460820 KB Output is correct
8 Correct 1012 ms 484360 KB Output is correct
9 Correct 1016 ms 484136 KB Output is correct
10 Correct 1042 ms 492940 KB Output is correct
11 Correct 1067 ms 493492 KB Output is correct
12 Incorrect 943 ms 6572 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 205 ms 1608 KB Output is correct
2 Correct 253 ms 13376 KB Output is correct
3 Correct 240 ms 12656 KB Output is correct
4 Correct 276 ms 13072 KB Output is correct
5 Correct 263 ms 11724 KB Output is correct
6 Correct 257 ms 11556 KB Output is correct
7 Correct 196 ms 1632 KB Output is correct
8 Correct 995 ms 399724 KB Output is correct
9 Correct 1079 ms 399672 KB Output is correct
10 Correct 204 ms 1476 KB Output is correct
11 Correct 855 ms 404592 KB Output is correct
12 Correct 985 ms 404496 KB Output is correct
13 Correct 788 ms 400284 KB Output is correct
14 Correct 200 ms 1616 KB Output is correct
15 Correct 984 ms 483020 KB Output is correct
16 Correct 1119 ms 460772 KB Output is correct
17 Correct 1038 ms 484248 KB Output is correct
18 Correct 1012 ms 484168 KB Output is correct
19 Correct 1027 ms 492948 KB Output is correct
20 Correct 1066 ms 493576 KB Output is correct
21 Correct 959 ms 405716 KB Output is correct
22 Correct 962 ms 413980 KB Output is correct
23 Correct 1075 ms 462060 KB Output is correct
24 Correct 1048 ms 461384 KB Output is correct
25 Correct 1008 ms 432560 KB Output is correct
26 Runtime error 688 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 205 ms 1608 KB Output is correct
2 Correct 253 ms 13376 KB Output is correct
3 Correct 240 ms 12656 KB Output is correct
4 Correct 276 ms 13072 KB Output is correct
5 Correct 263 ms 11724 KB Output is correct
6 Correct 257 ms 11556 KB Output is correct
7 Correct 196 ms 1632 KB Output is correct
8 Correct 995 ms 399724 KB Output is correct
9 Correct 1079 ms 399672 KB Output is correct
10 Correct 204 ms 1476 KB Output is correct
11 Correct 855 ms 404592 KB Output is correct
12 Correct 985 ms 404496 KB Output is correct
13 Correct 788 ms 400284 KB Output is correct
14 Correct 200 ms 1616 KB Output is correct
15 Correct 984 ms 483020 KB Output is correct
16 Correct 1119 ms 460772 KB Output is correct
17 Correct 1038 ms 484248 KB Output is correct
18 Correct 1012 ms 484168 KB Output is correct
19 Correct 1027 ms 492948 KB Output is correct
20 Correct 1066 ms 493576 KB Output is correct
21 Correct 959 ms 405716 KB Output is correct
22 Correct 962 ms 413980 KB Output is correct
23 Correct 1075 ms 462060 KB Output is correct
24 Correct 1048 ms 461384 KB Output is correct
25 Correct 1008 ms 432560 KB Output is correct
26 Runtime error 688 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -