Submission #399268

#	Time	Username	Problem	Language	Result	Execution time	Memory
399268		LucaDantas	Inside information (BOI21_servers)	C++17	50 / 100	313 ms	48964 KiB

servers

#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 (stderr)

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
• 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: 17.5 / 17.5
• Subtask 12: 0 / 17.5