제출 #1167351

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

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
const int N = 1e3 + 5;

int n;
arr<arr<int, N>, N> p;

arr<vec<int>, N> ln;
arr<int, N> ln_src;
void ln_dfs(int u, int src) {
	ln_src[u] = src, ln[src].push_back(u);
	for (int v = 1; v <= n; v++) {
		if (p[u][v] != 1) continue;
		if (ln_src[v]) continue;
		ln_dfs(v, src);
	}
}
void ln_cmp() {
	for (int u = 1; u <= n; u++) {
		if (ln_src[u]) continue;
		ln_dfs(u, u);
	}
	// for (int u = 1; u <= n; u++) {
	// 	for (int v : ln[u]) cout << v << " ";
	// 	cout << '\n';
	// }
}

arr<vec<int>, N> cnn;
arr<int, N> cnn_src;
void cnn_dfs(int u, int src) {
	cnn_src[u] = src, cnn[src].push_back(u);
	for (int v = 1; v <= n; v++) {
		if (!p[u][v]) continue;
		if (cnn_src[v]) continue;
		cnn_dfs(v, src);
	}
}
void cnn_cmp() {
	for (int u = 1; u <= n; u++) {
		if (cnn_src[u]) continue;
		cnn_dfs(u, u);
	}
	// for (int u = 1; u <= n; u++) {
	// 	for (int v : cnn[u]) cout << v << " ";
	// 	cout << '\n';
	// }
}

arr<arr<int, N>, N> ans;
void upd(int u, int v) { ans[u][v] = ans[v][u] = 1; }
bool ans_cmp() {
	for (int c = 1; c <= n; c++) {
		set<int> unq;
		for (int u : cnn[c]) unq.insert(ln_src[u]);
		if (unq.size() == 2) return false;

		for (auto it = unq.begin(); it != unq.end(); it++) {
			for (int i = 0; i < ln[*it].size() - 1; i++)
				upd(ln[*it][i], ln[*it][i + 1]);

			if (unq.size() == 1) continue;
			auto nx = (next(it, 1) == unq.end()) ? unq.begin() : next(it, 1);
			upd(*it, *nx);
		}
	}
	return true;
}

bool chck() {
	for (int u = 1; u <= n; u++) {
		for (int v = 1; v <= n; v++) {
			if (u == v) continue;

			if (cnn_src[u] != cnn_src[v]) {
				if (p[u][v] != 0) return false;
			} else if (ln_src[u] != ln_src[v]) {
				if (p[u][v] != 2) return false;
			} else {
				if (p[u][v] != 1) return false;
			}
		}
	}
	return true;
}

int construct(vec<vec<int>> _p) {
	n = _p.size();
	for (int u = 1; u <= n; u++)
		for (int v = 1; v <= n; v++)
			p[u][v] = _p[u - 1][v - 1];
	
	ln_cmp();
	cnn_cmp();
	if (!ans_cmp()) return 0;
	if (!chck()) return 0;

	vec<vec<int>> ans_lst(n);
	for (int u = 1; u <= n; u++) 
		for (int v = 1; v <= n; v++) 
			ans_lst[u - 1].push_back(ans[u][v]);
	build(ans_lst);

	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