Submission #311636

#	Time	Username	Problem	Language	Result	Execution time	Memory
311636		tfg	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	265 ms	22136 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <cassert>

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n, std::vector<int>(n, 0));
	std::vector<bool> wtf(n, false);
	for(int r = 0; r < n; r++) {
		if(wtf[r]) continue;
		std::vector<std::vector<int>> chains;
		std::vector<int> others;
		int lul = 2;
		for(int j = 0; j < n; j++) {
			if(p[r][j]) {
				if(wtf[j]) {
					return 0;
				}
				int x = 0;
				while(x < (int) chains.size() && p[j][chains[x][0]] != 1) {
					x++;
				}
				if(x == (int) chains.size()) {
					chains.emplace_back(0, 0);
				}
				chains[x].push_back(j);
				wtf[j] = true;
			} else {
				others.push_back(j);
			}
		}
		int m = (int) chains.size();
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < m; j++) {
				for(auto v1 : chains[i]) for(auto v2 : chains[j]) {
					lul = std::max(lul, p[v1][v2]);
				}
			}
		}
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < m; j++) {
				for(auto v1 : chains[i]) for(auto v2 : chains[j]) {
					int want = i == j ? 1 : lul;
					if(p[v1][v2] != want) {
						return 0;
					}
				}
			}
			for(auto v1 : chains[i]) {
				for(auto o : others) {
					if(p[v1][o] || p[o][v1]) {
						return 0;
					}
				}
			}
		}
		if(m == 1) {
			int last = -1;
			for(auto v : chains[0]) {
				if(last != -1) {
					answer[last][v] = answer[v][last] = 1;
				}
				last = v;
			}
		} else if(m == 2) {
			return 0;
		} else if(m != 4 && lul == 3) {
			return 0;
		} else {
			assert(m > 2);
			for(int i = 0; i < m; i++) {
				int u = chains[i][0], v = chains[(i+1)%m][0];
				answer[u][v] = answer[v][u] = 1;
			}
			if(lul == 3) {
				int u = chains[0][0], v = chains[2][0];
				answer[u][v] = answer[v][u] = 1;
			}
			for(auto chain : chains) {
				int last = -1;
				for(auto v : chain) {
					if(last != -1) {
						answer[last][v] = answer[v][last] = 1;
					}
					last = v;
				}
			}
		}
	}
	build(answer);
	return 1;
}

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