oj.uz

Submission #399268

# Submission time Handle Problem Language Result Execution time Memory
399268 2021-05-05T13:46:35 Z LucaDantas Inside information (BOI21_servers) C++17
50 / 100
 313 ms 48964 KB 
#include <cstdio>
#include <cassert>
#include <vector>

constexpr int maxn = 1e7+10;

int ptr = 0;

struct Node
{
	bool v;
	int l, r;
} tree[maxn];

int novo[maxn], antigo[maxn];

void create() {
	tree[ptr].l = tree[ptr].r = ptr;
	tree[ptr].v = 0;
	++ptr;
}

int set(int base, int l, int r, int pos) {
	int node = ptr; create();
	tree[node] = tree[base];
	tree[node].v = 1;
	if(l == r) return node;
	int m = (l+r) >> 1;
	if(pos <= m) tree[node].l = set(node, l, m, pos);
	else tree[node].r = set(node, m+1, r, pos);
	return node;
}

int merge(int a, int b) {
	if(tree[a].v && tree[b].v) {
		int node = ptr; create();
		tree[node].v = 1;
		tree[node].l = merge(tree[a].l, tree[b].l);
		tree[node].r = merge(tree[a].r, tree[b].r);
		return node;
	}
	if(tree[a].v) return a;
	return b;
}

int query(int node, int l, int r, int pos) {
	if(l == r) return tree[node].v;
	int m = (l+r) >> 1;
	if(pos <= m) return query(tree[node].l, l, m, pos);
	return query(tree[node].r, m+1, r, pos);
}

int main() {
	int n, k; scanf("%d %d", &n, &k);
	novo[0] = ptr; create();
	for(int i = 1; i <= n; i++)
		novo[i] = set(novo[0], 1, n, i);
	for(int i = 0; i < n + k - 1; i++) {
		char c; scanf(" %c", &c);
		if(c == 'S') {
			int a, b; scanf("%d %d", &a, &b);
			int node = merge(novo[a], novo[b]);
			novo[a] = node;
			novo[b] = node;
		} else if(c == 'Q') {
			int a, b; scanf("%d %d", &a, &b);
			puts(query(novo[a], 1, n, b) ? "yes" : "no");
		} else {
			assert(0);
		}
	}
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:54:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:59:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
servers.cpp:61:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |    int a, b; scanf("%d %d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:66:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |    int a, b; scanf("%d %d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 580 KB Output is correct
2 Correct 51 ms 1376 KB Output is correct
3 Correct 54 ms 1768 KB Output is correct
4 Correct 52 ms 1420 KB Output is correct
5 Correct 51 ms 1728 KB Output is correct
6 Correct 56 ms 1844 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 580 KB Output is correct
2 Correct 51 ms 1376 KB Output is correct
3 Correct 54 ms 1768 KB Output is correct
4 Correct 52 ms 1420 KB Output is correct
5 Correct 51 ms 1728 KB Output is correct
6 Correct 56 ms 1844 KB Output is correct
7 Runtime error 11 ms 392 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 676 KB Output is correct
2 Correct 313 ms 48784 KB Output is correct
3 Correct 303 ms 48768 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 676 KB Output is correct
2 Correct 313 ms 48784 KB Output is correct
3 Correct 303 ms 48768 KB Output is correct
4 Runtime error 11 ms 332 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 580 KB Output is correct
2 Correct 228 ms 48796 KB Output is correct
3 Correct 274 ms 48836 KB Output is correct
4 Correct 198 ms 48756 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 580 KB Output is correct
2 Correct 228 ms 48796 KB Output is correct
3 Correct 274 ms 48836 KB Output is correct
4 Correct 198 ms 48756 KB Output is correct
5 Runtime error 10 ms 380 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 560 KB Output is correct
2 Correct 207 ms 45416 KB Output is correct
3 Correct 240 ms 41916 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 560 KB Output is correct
2 Correct 207 ms 45416 KB Output is correct
3 Correct 240 ms 41916 KB Output is correct
4 Runtime error 10 ms 332 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 632 KB Output is correct
2 Correct 230 ms 48836 KB Output is correct
3 Correct 252 ms 48768 KB Output is correct
4 Correct 195 ms 48708 KB Output is correct
5 Correct 40 ms 532 KB Output is correct
6 Correct 205 ms 45432 KB Output is correct
7 Correct 230 ms 41924 KB Output is correct
8 Correct 190 ms 32432 KB Output is correct
9 Correct 202 ms 32580 KB Output is correct
10 Correct 253 ms 48852 KB Output is correct
11 Correct 273 ms 48800 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 632 KB Output is correct
2 Correct 230 ms 48836 KB Output is correct
3 Correct 252 ms 48768 KB Output is correct
4 Correct 195 ms 48708 KB Output is correct
5 Correct 40 ms 532 KB Output is correct
6 Correct 205 ms 45432 KB Output is correct
7 Correct 230 ms 41924 KB Output is correct
8 Correct 190 ms 32432 KB Output is correct
9 Correct 202 ms 32580 KB Output is correct
10 Correct 253 ms 48852 KB Output is correct
11 Correct 273 ms 48800 KB Output is correct
12 Runtime error 11 ms 332 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 652 KB Output is correct
2 Correct 51 ms 1476 KB Output is correct
3 Correct 54 ms 1784 KB Output is correct
4 Correct 51 ms 1348 KB Output is correct
5 Correct 51 ms 1732 KB Output is correct
6 Correct 59 ms 1732 KB Output is correct
7 Correct 38 ms 580 KB Output is correct
8 Correct 295 ms 48708 KB Output is correct
9 Correct 299 ms 48964 KB Output is correct
10 Correct 38 ms 608 KB Output is correct
11 Correct 224 ms 48836 KB Output is correct
12 Correct 225 ms 48732 KB Output is correct
13 Correct 199 ms 48708 KB Output is correct
14 Correct 39 ms 580 KB Output is correct
15 Correct 204 ms 45308 KB Output is correct
16 Correct 233 ms 42180 KB Output is correct
17 Correct 189 ms 32336 KB Output is correct
18 Correct 193 ms 32436 KB Output is correct
19 Correct 262 ms 48832 KB Output is correct
20 Correct 278 ms 48768 KB Output is correct
21 Correct 300 ms 48580 KB Output is correct
22 Correct 301 ms 48612 KB Output is correct
23 Correct 248 ms 41048 KB Output is correct
24 Correct 254 ms 41156 KB Output is correct
25 Correct 238 ms 39364 KB Output is correct
26 Correct 265 ms 46624 KB Output is correct
27 Correct 263 ms 48676 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 652 KB Output is correct
2 Correct 51 ms 1476 KB Output is correct
3 Correct 54 ms 1784 KB Output is correct
4 Correct 51 ms 1348 KB Output is correct
5 Correct 51 ms 1732 KB Output is correct
6 Correct 59 ms 1732 KB Output is correct
7 Correct 38 ms 580 KB Output is correct
8 Correct 295 ms 48708 KB Output is correct
9 Correct 299 ms 48964 KB Output is correct
10 Correct 38 ms 608 KB Output is correct
11 Correct 224 ms 48836 KB Output is correct
12 Correct 225 ms 48732 KB Output is correct
13 Correct 199 ms 48708 KB Output is correct
14 Correct 39 ms 580 KB Output is correct
15 Correct 204 ms 45308 KB Output is correct
16 Correct 233 ms 42180 KB Output is correct
17 Correct 189 ms 32336 KB Output is correct
18 Correct 193 ms 32436 KB Output is correct
19 Correct 262 ms 48832 KB Output is correct
20 Correct 278 ms 48768 KB Output is correct
21 Correct 300 ms 48580 KB Output is correct
22 Correct 301 ms 48612 KB Output is correct
23 Correct 248 ms 41048 KB Output is correct
24 Correct 254 ms 41156 KB Output is correct
25 Correct 238 ms 39364 KB Output is correct
26 Correct 265 ms 46624 KB Output is correct
27 Correct 263 ms 48676 KB Output is correct
28 Runtime error 10 ms 388 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -