oj.uz

Submission #678417

# Submission time Handle Problem Language Result Execution time Memory
678417 2023-01-05T20:46:31 Z NK_ Inside information (BOI21_servers) C++17
5 / 100
 2048 ms 524288 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 << (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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 191 ms 572 KB Output is correct
2 Correct 210 ms 3756 KB Output is correct
3 Correct 441 ms 49152 KB Output is correct
4 Correct 216 ms 3440 KB Output is correct
5 Correct 218 ms 3240 KB Output is correct
6 Correct 1428 ms 378416 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 191 ms 572 KB Output is correct
2 Correct 210 ms 3756 KB Output is correct
3 Correct 441 ms 49152 KB Output is correct
4 Correct 216 ms 3440 KB Output is correct
5 Correct 218 ms 3240 KB Output is correct
6 Correct 1428 ms 378416 KB Output is correct
7 Correct 184 ms 1424 KB Output is correct
8 Correct 196 ms 3464 KB Output is correct
9 Correct 396 ms 61192 KB Output is correct
10 Correct 193 ms 3020 KB Output is correct
11 Correct 208 ms 2904 KB Output is correct
12 Correct 1343 ms 378260 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 185 ms 856 KB Output is correct
2 Runtime error 1283 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 185 ms 856 KB Output is correct
2 Runtime error 1283 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 864 KB Output is correct
2 Correct 418 ms 41296 KB Output is correct
3 Correct 465 ms 41204 KB Output is correct
4 Runtime error 1274 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 864 KB Output is correct
2 Correct 418 ms 41296 KB Output is correct
3 Correct 465 ms 41204 KB Output is correct
4 Runtime error 1274 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 948 KB Output is correct
2 Runtime error 2048 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 948 KB Output is correct
2 Runtime error 2048 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 192 ms 988 KB Output is correct
2 Correct 415 ms 41152 KB Output is correct
3 Correct 461 ms 41252 KB Output is correct
4 Runtime error 1322 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 192 ms 988 KB Output is correct
2 Correct 415 ms 41152 KB Output is correct
3 Correct 461 ms 41252 KB Output is correct
4 Runtime error 1322 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1092 KB Output is correct
2 Correct 223 ms 3732 KB Output is correct
3 Correct 381 ms 49236 KB Output is correct
4 Correct 216 ms 3396 KB Output is correct
5 Correct 208 ms 3208 KB Output is correct
6 Correct 1453 ms 378428 KB Output is correct
7 Correct 188 ms 1604 KB Output is correct
8 Runtime error 1269 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1092 KB Output is correct
2 Correct 223 ms 3732 KB Output is correct
3 Correct 381 ms 49236 KB Output is correct
4 Correct 216 ms 3396 KB Output is correct
5 Correct 208 ms 3208 KB Output is correct
6 Correct 1453 ms 378428 KB Output is correct
7 Correct 188 ms 1604 KB Output is correct
8 Runtime error 1269 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -