Submission #678416

#	Time	Username	Problem	Language	Result	Execution time	Memory
678416		NK_	Inside information (BOI21_servers)	C++17	0 / 100	243 ms	1412 KiB

servers

#include <bits/stdc++.h>

using namespace std;

#define nl '\n';

using ll = long long;

int main() {
	int N, Q; cin >> N >> Q;

	vector<int> C(N, 1);

	vector<int> ID(N);
	vector<set<int>> S(2 * N);
	for(int i = 0; i < N; i++) {
		ID[i] = i;
		S[i] = {i};
	}

	int X = N;

	for(int t = 0; t < (N + Q - 1); t++) {
		char c; cin >> c;
		if (c == 'S') {
			int u, v; cin >> u >> v; --u, --v;

			int U = ID[u], V = ID[v];

			if (size(S[U]) < size(S[V])) swap(U, V);

			for(auto &x : S[U]) {
				S[X].insert(x);
				C[x]++;
			}

			for(auto &x : S[V]) {
				S[X].insert(x);
				C[x]++;
			}

			// cout << "DONE" << nl;
			// cout << u << " " << v << nl;
			// for(auto x : S[X]) cout << x << " ";
			// cout << nl;

			ID[u] = ID[v] = X++;
		}

		if (c == 'Q') {
			int u, d; cin >> u >> d; --u, --d;
			u = ID[u]; cout << u << " " << d << nl;
			cout << (S[u].count(d) ? "yes" : "no") << nl;
		}

		if (c == 'C') {
			int x; cin >> x; --x;
			cout << C[x] << nl;
		}
	}




}

/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6


4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4 

*/

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