제출 #993198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993198		Newtonabc	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	128 ms	22096 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int pa[N];
bool cy[N][N];
int root(int x){
	if(pa[x]==x) return x;
	else return pa[x]=root(pa[x]);
}
int construct(vector<vector<int> > p) {
	int n = p.size();
	vector<vector<int> > answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(n,0);
		answer.push_back(row);
	}
	for(int i=0;i<n;i++) pa[i]=i;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==1 && root(i)!=root(j)){
				answer[i][j]=1;
				answer[j][i]=1;
				pa[root(i)]=root(j);
			}
			if(p[i][j]==3) return 0;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int a,b;
			if(p[i][j]==2){
				a=root(i),b=root(j);
				if(a==b) return 0;
				if(cy[a][b]) continue;
				answer[a][b]=1;
				answer[b][a]=1;
				cy[a][b]=1,cy[b][a]=1;
			}
		}
	}
	build(answer);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4