Submission #303295

#	Time	Username	Problem	Language	Result	Execution time	Memory
303295		miello	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	267 ms	22160 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;
const int MXN = 1005;

vector<int> par(MXN), cycle, line[MXN];
vector<int> cycle_vertex;

int root(int i) {
	while(i != par[par[i]]) {
		par[i] = par[par[i]];
		i = par[par[i]];
	}
	return i;
}

void mergeset(int a, int b) {
	par[root(a)] = root(b);
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
		par[i] = i;
	}
	for(int i = 0; i < n; i++) {
		int sum = 0;
		for(int j = 0; j < n; j++) {
			if(i == j) {
				continue;
			}
			sum += p[i][j];
			if(p[i][j] == 1) {
				if(root(i) != root(j)) {
					mergeset(i, j);
				}
			}
		}
		if(sum == 0) {
			par[i] = -1;
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(i == j) continue;
			if(par[i] == -1 || par[j] == -1) {
				if(p[i][j] != 0) {
					return 0;
				}
			} else if(root(i) == root(j)) {
				if(p[i][j] != 1) {
					return 0;
				}
			} else if(root(i) != root(j)) {
				if(p[i][j] != 2) {
					return 0;
				}
			} else if(p[i][j] == 3) {
				return 0;
			}
		}
	}
	for(int i = 0; i < n; i++) {
		if(par[i] != -1) {
			line[root(i)].push_back(i);
		}
	}
	for(int i = 0; i < n; i++) {
		int sz = line[i].size();
		if(sz) {
			cycle_vertex.push_back(line[i][0]);
		}
		for(int j = 0; j < sz - 1; j++) {
			answer[line[i][j]][line[i][j + 1]] = 1;
			answer[line[i][j + 1]][line[i][j]] = 1;
		}
	} 
	int sz = cycle_vertex.size();
	if(sz >= 3) {
		cycle_vertex.push_back(cycle_vertex[0]);
		for(int i = 0; i < sz; i++) {
			answer[cycle_vertex[i]][cycle_vertex[i + 1]] = 1;
			answer[cycle_vertex[i + 1]][cycle_vertex[i]] = 1;
		}
	}
	build(answer);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4