oj.uz

Submission #381115

# Submission time Handle Problem Language Result Execution time Memory
381115 2021-03-24T14:54:41 Z BlancaHM Carnival (CEOI14_carnival) C++14
20 / 100
 117 ms 1260 KB 
#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
using namespace std;

vector<int> par;
int numSets;
vector<unordered_set<int>> enemies;

int root(int a) {
	if (a == par[a])
		return a;
	return par[a] = root(par[a]);
}

void merge(int i, int j) {
	int root_i = root(i), root_j = root(j);
	if (root_i == root_j)
		return;
	numSets--;
	par[root_j] = root_i;
	for (int u: enemies[root_j]) {
		enemies[root_i].insert(u);
		enemies[root(u)].insert(root_i);
	}
}

void separate(int i, int j) {
	int root_i = root(i), root_j = root(j);
	enemies[root_i].insert(root_j);
	enemies[root_j].insert(root_i);
}

void solve(int N, int C) {
	numSets = N;
	par = vector<int>(N);
	for (int i = 0; i < N; i++)
		par[i] = i;
	enemies.assign(150, unordered_set<int>());
	int ans;
	for (int i = 0; i < N; i++) {
		if (numSets == C)
			break;
		for (int j = i+1; j < N; j++) {
			if (numSets == C)
				break;
			if (root(i) == root(j) || enemies[root(i)].find(root(j)) != enemies[i].end())
				continue;
			cout << "2 " << (i+1) << " " << j+1 << '\n';
			cin >> ans;
			if (ans == 1)
				merge(i, j);
			else
				separate(i, j);
		}
	}
}

int main() {
	int N, C;
	cin >> N;
	cout << N;
	for (int i = 1; i <= N; i++)
		cout << " " << i;
	cout << '\n';
	cin >> C;
	solve(N, C);
	map<int, int> roots;
	int c = 1;
	for (int i = 0; i < N; i++) {
		if (roots.find(root(i)) == roots.end()) {
			roots[root(i)] = c++;
		}
	}
	int costumes[N];
	for (int i = 0; i < N; i++)
		costumes[i] = roots[root(i)];
	cout << "0";
	for (int i = 0; i < N; i++)
		cout << " " << costumes[i];
	cout << '\n';
	return 0;
}

Subtask #1
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 412 KB Output is correct
2 Correct 27 ms 600 KB Output is correct
3 Partially correct 80 ms 1032 KB Partially correct
4 Partially correct 76 ms 924 KB Partially correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 15 ms 492 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 400 KB Output is correct
2 Correct 28 ms 588 KB Output is correct
3 Partially correct 33 ms 748 KB Partially correct
4 Partially correct 80 ms 1040 KB Partially correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 3 ms 400 KB Output is correct
7 Correct 6 ms 364 KB Output is correct

Subtask #3
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 9 ms 420 KB Output is correct
3 Partially correct 72 ms 684 KB Partially correct
4 Partially correct 107 ms 1148 KB Partially correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 36 ms 512 KB Output is correct

Subtask #4
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 7 ms 416 KB Output is correct
3 Partially correct 80 ms 1132 KB Partially correct
4 Partially correct 117 ms 1132 KB Partially correct
5 Correct 4 ms 364 KB Output is correct
6 Correct 7 ms 364 KB Output is correct
7 Correct 26 ms 492 KB Output is correct

Subtask #5
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 16 ms 492 KB Output is correct
3 Partially correct 75 ms 960 KB Partially correct
4 Partially correct 85 ms 876 KB Partially correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Partially correct 110 ms 1260 KB Partially correct