oj.uz

Submission #678416

# Submission time Handle Problem Language Result Execution time Memory
678416 2023-01-05T20:45:56 Z NK_ Inside information (BOI21_servers) C++17
0 / 100
 243 ms 1412 KB 
#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

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 1412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 1412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 1388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 1388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 1308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 1308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 1360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 1360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 243 ms 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 243 ms 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -