oj.uz

Submission #351282

# Submission time Handle Problem Language Result Execution time Memory
351282 2021-01-19T20:10:53 Z BlancaHM Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 277 ms 22380 KB 
#include <iostream>
#include <vector>
#include <unordered_map>
#include "supertrees.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int root(int a, vector<int> & parent) {
	if (a == parent[a])
		return a;
	return parent[a] = root(parent[a], parent);
}

void merge(int i, int j, vector<int> & parent, vector<int> & rnk, int & numCCs) {
	int root_i = root(i, parent), root_j = root(j, parent);
	if (root_i == root_j) return;
	numCCs--;
	if (rnk[i] != rnk[j]) {
		if (rnk[i] > rnk[j]) parent[root_j] = parent[root_i];
		else parent[root_i] = parent[root_j];
	} else {
		parent[root_i] = parent[root_j];
		rnk[j]++;
	}
}

int construct(vvi p) {
	int N = (int) p.size(), numCCs = N;
	vector<int> parent(N), rnk(N, 0);
	for (int i = 0; i < N; i++)
		parent[i] = i;
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (p[i][j]) {
				if (p[i][j] == 3) {
					return 0;
				}
				merge(i, j, parent, rnk, numCCs);
			} else if (root(i, parent) == root(j, parent))
				return 0;
		}
	}
	unordered_map<int, int> roots;
	int c = 0;
	for (int i = 0; i < N; i++) {
		if (parent[i] == i)
			roots[i] = c++;
	}
	vvi CCs(numCCs, vi());
	for (int i = 0; i < N; i++)
		CCs[roots[root(i, parent)]].push_back(i);

	vi allTwos, rest;
	vvi result(N, vi(N, 0));
	bool twos;
	for (int i = 0; i < numCCs; i++) {
		if ((int) CCs[i].size() == 1) continue;
		allTwos.clear();
		rest.clear();
		for (int j = 0; j < (int) CCs[i].size(); j++) {
			twos = true;
			for (int k = 0; k < (int) CCs[i].size(); k++) {
				if (k == j) continue;
				if (p[CCs[i][j]][CCs[i][k]] == 1) {
					twos = false;
					break;
				}
			}
			if (twos) allTwos.push_back(CCs[i][j]);
			else rest.push_back(CCs[i][j]);
		}
		for (int i = 0; i < (int) allTwos.size()-1; i++)
			result[allTwos[i]][allTwos[i+1]] = result[allTwos[i+1]][allTwos[i]] = 1;
		for (int i = 0; i < (int) rest.size()-1; i++)
			result[rest[i]][rest[i+1]] = result[rest[i+1]][rest[i]] = 1;
		if ((int) allTwos.size() == 1) return 0;
		if (rest.empty())
			result[allTwos[0]][allTwos[(int) allTwos.size()-1]] = result[allTwos[(int) allTwos.size()-1]][allTwos[0]] = 1;
		else if (allTwos.size())
			result[allTwos[0]][rest[0]] = result[rest[0]][allTwos[0]] = result[rest[0]][allTwos[(int) allTwos.size()-1]] = result[allTwos[(int) allTwos.size()-1]][rest[0]] = 1;
	}
	build(result);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 11 ms 1260 KB Output is correct
7 Correct 258 ms 22380 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 11 ms 1260 KB Output is correct
7 Correct 258 ms 22380 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1260 KB Output is correct
13 Correct 251 ms 22380 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 106 ms 8300 KB Output is correct
18 Incorrect 1 ms 384 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 68 ms 5976 KB Output is correct
5 Correct 255 ms 22252 KB Output is correct
6 Correct 260 ms 22252 KB Output is correct
7 Correct 259 ms 22252 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 68 ms 6124 KB Output is correct
10 Correct 271 ms 22252 KB Output is correct
11 Correct 257 ms 22284 KB Output is correct
12 Correct 277 ms 22208 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Incorrect 27 ms 3820 KB Answer gives possible 0 while actual possible 1
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 11 ms 1260 KB Output is correct
7 Correct 258 ms 22380 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1260 KB Output is correct
13 Correct 251 ms 22380 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 106 ms 8300 KB Output is correct
18 Incorrect 1 ms 384 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 11 ms 1260 KB Output is correct
7 Correct 258 ms 22380 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1260 KB Output is correct
13 Correct 251 ms 22380 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 106 ms 8300 KB Output is correct
18 Incorrect 1 ms 384 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -