제출 #475204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475204		cs71107	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	288 ms	24152 KiB

supertrees

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

using namespace std;

const int MAXM = 1e3+10;

struct UF{

	int par[MAXM];

	void init(int n){
		for(int i=0;i<n;i++){
			par[i] = i;
		}
		return;
	}

	int root(int x){
		if(par[x]==x)return x;
		else return par[x] = root(par[x]);
	}

	void mymerge(int a,int b){
		a = root(a);
		b = root(b);
		par[b] = a;
		return;
	}

	int getdiff(int a,int b){
		if(root(a)^root(b))return 1;
		else return 0;
	}

}uf0,uf1;

vector<int> id[MAXM];

int construct(std::vector<std::vector<int>> p) {

	
	int res = 1;
	int n = p.size();

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]==3){
				res = 0;
				break;
			}
		}
		if(!res)break;
	}

	if(!res)return 0;

	uf0.init(n);	

	int a,b;

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]==1){
				uf0.mymerge(i,j);
			}
		}
	}

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]^1){
				res&=uf0.getdiff(i,j);
			}
		}
	}

	if(!res)return 0;

	uf1.init(n);

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]==2){
				a = uf0.root(i);
				b = uf0.root(j);

				uf1.mymerge(a,b);
			}			
		}
	}

	for(int i=0;i<n;i++){
	
		for(int j=i+1;j<n;j++){
			if(p[i][j]==0){
				res&=uf1.getdiff(uf0.root(i),uf0.root(j));
			}
		}
	}

	if(!res)return 0;

	for(int i=0;i<n;i++){
		a = uf0.root(i);
		if(a^i)continue;
		b = uf1.root(i);

		id[b].push_back(i);
	}

	for(int i=0;i<n;i++){
		if((int)id[i].size()==2){
			res = 0;
			break;
		}
	}

	if(!res)return 0;

	vector<vector<int> > answer(n);

	for(int i=0;i<n;i++){
		answer[i] = vector<int> (n,0);
	}

	for(int i=0;i<n;i++){
		a = uf0.root(i);
		if(a^i){
			answer[i][a] = 1;
			answer[a][i] = 1;
		}
	}

	int cursz = 0;

	for(int i=0;i<n;i++){
		cursz = (int)id[i].size();

		if(cursz>=3){
			for(int j=0;j<cursz;j++){
				answer[id[i][j]][id[i][(j+1)%cursz]] = 1;
				answer[id[i][(j+1)%cursz]][id[i][j]] = 1;
			}
		}
	}

	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