제출 #1039750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039750		amirhoseinfar1385	슈퍼트리 잇기 (IOI20_supertrees)	C++17	0 / 100	1 ms	348 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int n,vis[maxn];
vector<vector<int>>res;

struct dsu{
	int par[maxn];
	vector<int>adj[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
		}
	}
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(int u,int v){
		u=root(u),v=root(v);
		if(u!=v){
			par[u]=v;
			adj[v].push_back(u);
		}
	}
	vector<int>ret;
	void dfs(int u,int par=-1){
		ret.push_back(u);
		for(auto x:adj[u]){
			if(x==par){
				continue;
			}
			dfs(x,u);
		}
	}
	vector<int>allc(int u){
		ret.clear();
		u=root(u);
		dfs(u);
		return ret;
	}
}ds1,ds2;

void adde(int u,int v){
	res[u][v]=res[v][u]=1;
}

void addp(vector<int>a){
	for(int i=1;i<(int)a.size();i++){
		adde(a[i-1],a[i]);
	}
}

int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	res.resize(n,vector<int>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j){
				continue;
			}
			if(p[i][j]==1){
				ds1.con(i,j);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			vector<int>hey=ds1.allc(i);
			for(auto x:hey){
				vis[x]=1;
			}
			addp(hey);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==2){
				ds2.con(ds1.root(i),ds1.root(j));
			}
		}
		vis[i]=0;
	}
	int retrr=1;
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			vector<int>hey=ds2.allc(i);
			for(auto x:hey){
				vis[x]=1;
			}
			addp(hey);
			if((int)hey.size()>2){
				adde(hey[0],hey.back());
			}
			if((int)hey.size()==1){
				retrr=-1;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j){
				continue;
			}
			if(p[i][j]==1&&ds1.root(i)!=ds1.root(j)){
				retrr=-1;
			}
			if(p[i][j]==0&&(ds1.root(i)==ds1.root(j)||ds2.root(ds1.root(i))==ds2.root(ds1.root(j)))){
				retrr=-1;
			}
			if(p[i][j]==2&&(ds2.root(ds1.root(i))!=ds2.root(ds1.root(j))||ds1.root(i)==ds1.root(j))){
				retrr=-1;
			}
		}
	}
	if(retrr==-1){
		return 0;
	}
	build(res);
	return retrr;
}

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