제출 #1149056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149056		blackslex	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	161 ms	26116 KiB

supertrees

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

using namespace std;

bool ck (vector<vector<int>> p, vector<vector<int>> answer) {
	int n = p.size();
	vector<vector<int>> v(n, vector<int>()), ans(n, vector<int>(n));
	vector<bool> f(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (answer[i][j]) v[i].emplace_back(j);
		}
	}
	auto dfs = [&] (auto &&dfs, int st, int cur) {
		if (f[cur]) return; f[cur] = 1;
		ans[st][cur]++;
		for (auto &e: v[cur]) {
			dfs(dfs, st, e);
		}
		f[cur] = 0;
	};
	for (int i = 0; i < n; i++) {
		dfs(dfs, i, i);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ans[i][j] != p[i][j]) return 0;
		}
	}
	return 1;
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n, vector<int>(n));
	auto add = [&] (int x, int y) {
		answer[x][y] = answer[y][x] = 1;
	};
	vector<int> par(n), par2(n);
	iota(par.begin(), par.end(), 0);
	iota(par2.begin(), par2.end(), 0);
	function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
	function<int(int)> fset2 = [&] (int x) {return (par2[x] == x ? x : par2[x] = fset2(par2[x]));};
	auto mg = [&] (int x, int y) {
		if ((x = fset(x)) == (y = fset(y))) return;
		par[y] = x;
	};
	auto mg2 = [&] (int x, int y) {
		if ((x = fset2(x)) == (y = fset2(y))) return;
		par2[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, cc;
		for (int j = 0; j < n; j++) {
			if (fset(j) == i) c.emplace_back(j);
		}
		int csz = c.size();
		for (int j = 0; j < csz; j++) {
			for (int k = 0; k < csz; k++) {
				if (c[j] != c[k] && p[c[j]][c[k]] == 1) mg2(c[j], c[k]);
			}
		}
		for (int j = 0; j < csz; j++) {
			if (fset2(c[j]) != c[j]) continue;
			cc.emplace_back(c[j]);
			vector<int> c2;
			for (int k = 0; k < csz; k++) {
				if (fset2(c[k]) == c[j]) c2.emplace_back(c[k]);
			}
			int csz2 = c2.size();
			for (int k = 0; k < csz2 - 1; k++) {
				add(c2[k], c2[k + 1]);
			}
		}
		sort(cc.begin(), cc.end()); cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
		int ccsz = cc.size();
		for (int j = 0; j < ccsz; j++) {
			add(cc[j], cc[(j + 1) % ccsz]);
		}
	}
	for (int i = 0; i < n; i++) {
		answer[i][i] = 0;
	}
	auto res = ck(p, answer);
	if (!res) return 0;
	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