제출 #1172508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172508		hyakup	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	120 ms	22240 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> adj(n, vector<int>(n));
	vector<int> pai(n), comp[n];
	iota( pai.begin(), pai.end(), 0 );
	for( int i = 0; i < n; i++ ) comp[i].push_back(i);

	function<int(int)> find = [&]( int a ){ return (( a == pai[a]) ? a : pai[a] = find(pai[a]) ); };

	auto join = [&]( int a, int b ){
		a  = find(a); b = find(b);
		if( a == b ) return 1;
		pai[b] = a;
		adj[a][b] = 1;
		adj[b][a] = 1;

		int ok = 1;
		for( int i : comp[a] ) for( int j : comp[b] ) if( p[i][j] != 1 ) ok = 0;
		for( int i : comp[b] ) comp[a].push_back(i);

		return ok;
	};


	for( int i = 0; i < n; i++ ) for( int j = i + 1; j < n; j++ ) if( (p[i][j] == 1 && !join( i, j )) || p[i][j] == 3 ) return 0;

	vector<int> marc(n);

	for( int i = 0; i < n; i++ ) if( pai[i] == i && !marc[i] ){
		queue<int> fila; fila.push(i);
		vector<int> ciclo;
		marc[i] = true;
		while( !fila.empty() ){
			int cur = fila.front(); fila.pop();
			ciclo.push_back(cur);
			for( int j = 0; j < n; j++ ) if( pai[j] == j && !marc[j] && p[cur][j] == 2 ) fila.push(j), marc[j] = true;
		}

		if( ciclo.size() < 2 ) continue;
		if( ciclo.size() == 2 ) return 0;

		for( int j = 0; j < ciclo.size(); j++ ) for( int k = j + 1; k < ciclo.size(); k++ )
			for( int a : comp[ciclo[j]] ) for( int b : comp[ciclo[k]] ) if( p[a][b] != 2 ) return 0;

		for( int i = 0; i + 1 < ciclo.size(); i++ ) adj[ciclo[i]][ciclo[i + 1]] = adj[ciclo[i + 1]][ciclo[i]] = 1;
		adj[i][ciclo.back()] = adj[ciclo.back()][i] = 1;
	}

	build(adj);

	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