Submission #1149005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149005		blackslex	슈퍼트리 잇기 (IOI20_supertrees)	C++20	11 / 100	119 ms	22168 KiB

supertrees

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

using namespace std;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n, vector<int>(n));
	vector<int> par(n); iota(par.begin(), par.end(), 0);
	function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
	auto mg = [&] (int x, int y) {
		if ((x = fset(x)) == (y = fset(y))) return;
		par[y] = x;
	};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j]) mg(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		if (fset(i) != i) continue;
		vector<int> c;
		for (int j = 0; j < n; j++) {
			if (fset(j) == i) c.emplace_back(j);
		}
		for (int j = 0; j < c.size() - 1; j++) {
			answer[c[j]][c[j + 1]] = answer[c[j + 1]][c[j]] = 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