Submission #1168287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168287		Troll321	Inside information (BOI21_servers)	C++20	10 / 100	39 ms	8520 KiB

servers

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<bool, bool> pbb;
const ll MAXN = 120000 + 5;
const ll MAXQ = 2*MAXN;

// 5 5
// S 1 2
// S 3 4
// S 5 4
// S 2 3
// C 1
// C 2
// C 3
// C 4
// C 5

// 48 1
// S 44 45
// S 21 20
// S 34 35
// S 2 3
// S 16 17
// S 47 46
// S 19 20
// S 5 6
// S 29 30
// S 44 43
// S 42 43
// S 17 18
// S 6 7
// S 36 37
// S 12 13
// S 31 30
// S 22 23
// S 24 25
// S 38 39
// S 45 46
// Q 42 26
// S 1 2
// S 3 4
// S 4 5
// S 7 8
// S 8 9
// S 9 10
// S 10 11
// S 11 12
// S 13 14
// S 14 15
// S 15 16
// S 18 19
// S 21 22
// S 23 24
// S 25 26
// S 26 27
// S 27 28
// S 28 29
// S 31 32
// S 32 33
// S 33 34
// S 35 36
// S 37 38
// S 39 40
// S 40 41
// S 41 42
// S 47 48


ll n, k;
pll range[MAXN];
// {L, R}
pbb extend[MAXN];
// {Lext, Rext}
pair<char, pll> query[MAXQ];
// {Type, {a, b}}

void addEdge(ll a, ll b) {
	if(a > b) {swap(a,b);}

	// Extend A
	extend[a].se = ((range[b].se - range[b].fi) == 0);

	// Extend B
	extend[b].fi = ((range[a].se - range[a].fi) == 0);

	range[a].se = b;
	range[b].fi = a;
}

pll findL(ll x) {
	if(extend[x].fi && range[x].fi != x) {
		pll out = findL(range[x].fi);
		range[x].fi = out.fi;
		extend[x].fi = out.se;
		return {range[x].fi, extend[x].fi};
	}
	return {range[x].fi, extend[x].fi};
}
// {Range, Ext}

pll findR(ll x) {
	if(extend[x].se && range[x].se != x) {
		pll out = findR(range[x].se);
		range[x].se = out.fi;
		extend[x].se = out.se;
		return {range[x].se, extend[x].se};
	}
	return {range[x].se, extend[x].se};
}

pll find(ll x) {
	return {findL(x).fi, findR(x).fi};
}

void data(ll a, ll b) {
	// Apakah B nyampe A
	pll out = find(b);
	cout << ((out.fi <= a && a <= out.se) ? "yes" : "no") << "\n";
}

void count(ll a) {
	pll out = find(a);
	cout << (out.se - out.fi + 1) << "\n";
}

void input() {
	cin >> n >> k;

	for (int i = 1; i <= n; ++i) {
		range[i] = {i,i};
		extend[i] = {true, true};
	}

	for (int i = 1; i <= n+k-1; ++i) {
		cin >> query[i].fi;
		switch(query[i].fi) {
		case 'S':
			cin >> query[i].se.fi >> query[i].se.se;
			addEdge(query[i].se.fi, query[i].se.se);
			// cout << extend[query[i].se.fi].fi << " " << extend[query[i].se.fi].se << "|\n";
			// cout << extend[query[i].se.se].fi << " " << extend[query[i].se.se].se << "|\n";
			// cout << "---\n";

			break ;
		case 'Q':
			cin >> query[i].se.fi >> query[i].se.se;
			data(query[i].se.fi, query[i].se.se);
			break ;
		case 'C':
			cin >> query[i].se.fi;
			count(query[i].se.fi);
			break ;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	input();
	// for (int i = 1; i <= n; ++i) {
	// 	cout << find(i).fi << " " << find(i).se << "\n";
	// }
	return 0;
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18