oj.uz

Submission #351200

# Submission time Handle Problem Language Result Execution time Memory
351200 2021-01-19T15:49:00 Z BlancaHM Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 512 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[j] = parent[i];
		else parent[i] = parent[j];
	} else {
		parent[i] = parent[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++) {
		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 (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 (allTwos.size() && (int) allTwos.size() <= 2) return 0;
		if (rest.empty())
			result[allTwos[0]][*allTwos.rbegin()] = result[*allTwos.rbegin()][allTwos[0]] = 1;
		else if (allTwos.size())
			result[allTwos[0]][rest[0]] = result[rest[0]][allTwos[0]] = result[rest[0]][*allTwos.rbegin()] = result[*allTwos.rbegin()][rest[0]] = 1;
	}
	build(result);
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 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 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -