제출 #616001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
616001		yanndev	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	244 ms	30312 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;

const int MX = 1042;

bool vis[MX];
bool vis2[MX];

int cycleId[MX];
int rep[MX];
int cycleRep[MX];
int compId[MX];

int nxtComp = 0;
int nxtCycle = 0;

vector<int> adj[MX];
vector<int> adj2[MX];

vector<int> comp[MX];
vector<int> comp2[MX];

void dfs(int node, int r, int c) {
	vis[node] = true;
	rep[node] = r;
	compId[node] = c;
	comp[c].push_back(node);

	for (auto& x: adj[node])
		if (!vis[x])
			dfs(x, r, c);
}

void dfs2(int node, int r, int c) {
	vis2[node] = true;
	cycleRep[node] = r;
	cycleId[node] = c;
	comp2[c].push_back(node);

	for (auto& x: adj2[node])
		if (!vis2[x])
			dfs2(x, r, c);
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	
	vector<vector<int>> answer;

	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 3)
				return 0;
			if (p[i][j] == 1 && i != j) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			//cout << "dfs root " << i << '\n';
			dfs(i, i, nxtComp++);
		}
	}

	for (int i = 0; i < n; i++) {
		if (rep[i] == i) {
			// add cycles
			for (int j = 0; j < n; j++) {
				if (rep[j] != i) {
					for (auto& x: comp[compId[i]]) {
						if (p[j][x] == 2) {
							//cout << "fuke " << i << ' ' << rep[j] << '\n';
							adj2[i].push_back(rep[j]);
							adj2[rep[j]].push_back(i);
						}
					}
				}
			}

			// add chain
			for (int j = 0; j + 1 < (int)comp[compId[i]].size(); j++) {
				answer[comp[compId[i]][j]][comp[compId[i]][j + 1]] = answer[comp[compId[i]][j + 1]][comp[compId[i]][j]] = 1;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (!vis2[i]) {
			dfs2(i, i, nxtCycle++);
		}
	}

	// add cycle edges
	for (int i = 0; i < n; i++) {
		if (rep[i] == i) {
			//cout << "comp of " << i << '\n';
			for (auto& x: comp[compId[i]]) {
				//cout << x << '\n';
				cycleId[x] = cycleId[i];
			}
		}

		if (cycleRep[i] == i) {
			int sz = (int)comp2[cycleId[i]].size();
			if (sz == 2)
				return 0;
			for (int j = 0; sz > 1 && j < sz; j++) {
				answer[comp2[cycleId[i]][j]][comp2[cycleId[i]][(j + 1) % sz]] = 1;
				answer[comp2[cycleId[i]][(j + 1) % sz]][comp2[cycleId[i]][j]] = 1;
				//cout << "cycle edge from " << comp2[cycleId[i]][j] << ' ' << comp2[cycleId[i]][j + 1] << '\n';
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i != j) {
				if (p[i][j] == 0 && cycleId[i] == cycleId[j])
					return 0;
				if (p[i][j] == 1 && rep[i] != rep[j])
					return 0;
				if (p[i][j] == 2 && !((cycleId[i] == cycleId[j]) && (rep[i] != rep[j])))
					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