Submission #659721

#	Time	Username	Problem	Language	Result	Execution time	Memory
659721		ymm	Inside information (BOI21_servers)	C++17	100 / 100	1414 ms	8544 KiB

servers

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1<<17;
const int S = 256;

int cnt[N];
unsigned char cnt_buf[S]; int buf_sum = 0;
unsigned char pool[2*N][S];
int pool_size;
int ptr_pool[N];

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void merge(int i, int j)
{
	if (ptr_pool[i] == -1 && ptr_pool[j] == -1)
		return;
	++buf_sum;
	if (ptr_pool[i] == -1)
		swap(i, j);
	if (ptr_pool[j] == -1) {
		i = ptr_pool[i];
		Loop (k,0,S)
			cnt_buf[k] -= pool[i][k];
		ptr_pool[j] = i;
		return;
	}
	int z = pool_size++;
	int tmp;
	tmp = ptr_pool[i]; ptr_pool[i] = z; i = tmp;
	tmp = ptr_pool[j]; ptr_pool[j] = z; j = tmp;
	Loop (k,0,S) {
		cnt_buf[k] -= pool[i][k] ^ pool[j][k];
		pool[z][k] = pool[i][k] | pool[j][k];
	}
}

void buf_flush()
{
	buf_sum = 0;
	Loop (i,0,S) {
		cnt[i] += cnt_buf[i];
		cnt_buf[i] = 0;
	}
}

int get_count(int i)
{
	return cnt[i] + cnt_buf[i];
}
bool has(int i, int j)
{
	if (ptr_pool[i] == -1)
		return false;
	i = ptr_pool[i];
	return pool[i][j];
}

void init(int off)
{
	buf_sum = 0;
	pool_size = S;
	Loop (i,0,S) {
		cnt[i] = 1;
		cnt_buf[i] = 0;
	}
	Loop (i,0,N)
		ptr_pool[i] = -1;
	Loop (i,0,S) {
		ptr_pool[i+off] = i;
		Loop (j,0,S)
			pool[i][j] = 0;
		pool[i][i] = -1;
	}
}

int qans[N*2];

struct {
	char type;
	int a, b;
} qr[N*2];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	q = n+q-1;
	Loop (i,0,q) {
		cin >> qr[i].type;
		switch (qr[i].type) {
		case 'S':
		case 'Q':
			cin >> qr[i].a >> qr[i].b;
			break;
		case 'C':
			cin >> qr[i].a;
			break;
		}
		--qr[i].a; --qr[i].b;
	}
	for (int off = 0; off < n; off += S) {
		init(off);
		Loop (i,0,q) {
			int a = qr[i].a;
			int b = qr[i].b;
			switch (qr[i].type) {
			case 'S':
				merge(a, b);
				break;
			case 'Q':
				if (off <= b && b < off + S)
					qans[i] = has(a, b-off);
				break;
			case 'C':
				if (off <= a && a < off + S)
					qans[i] = get_count(a-off);
				break;
			}
			if (buf_sum == 255)
				buf_flush();
		}
	}
	Loop (i,0,q) {
		switch (qr[i].type) {
		case 'Q': cout << (qans[i]? "yes": "no") << '\n'; break;
		case 'C': cout << qans[i] << '\n'; break;
		}
	}
}

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