제출 #1183408

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

supertrees

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


vector<int>parent;

int find(int p){
	if (parent[p]==p) return p;
	else return parent[p]=find(parent[p]);
}

void unite(int p1, int p2){
	p1=find(p1); p2=find(p2);
	parent[p1]=p2;
	return;
}

int construct(vector<vector<int> > p) {
	int n=p.size();
	parent.resize(n);
	for (int i=0; i<n; i++) parent[i]=i;
	vector<vector<int> >answer(n, vector<int>(n, 0));
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (p[i][j]==1){
				if (find(i)!=find(j)){
					for (int k=0; k<n; k++){
						if (p[i][k]!=p[j][k]) return 0;
					}
					answer[i][j]=1;
					answer[j][i]=1;
					unite(i, j);
				}
			}
		}
	}
	vector<int>c;
	for (int i=0; i<n; i++){
		if (parent[i]==i) c.push_back(i);
	}
	for (int i: c){
		for (int j: c){
			if (p[i][j]==3) return 0;
			else if (p[i][j]==2){
				if (find(i)!=find(j)) unite(i, j);
			} 
		}
	}
	for (int i: c){
		int ant=i;
		int ant2=-1;
		for (int j: c){
			if (find(j)==i && i!=j){
				if (ant2==-1) ant2=j;
				answer[j][ant]=1;
				answer[ant][j]=1;
				ant=j;
			}
		}if (ant2==ant) return 0;
		if (ant!=i){
			answer[i][ant]=1;
			answer[ant][i]=1;
		}
	}
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (p[i][j]==0 && find(i)==find(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