Submission #800073

#	Time	Username	Problem	Language	Result	Execution time	Memory
800073		alvingogo	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	183 ms	22088 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
	vector<int> bo;
	void init(int x){
		bo.resize(x);
		iota(bo.begin(),bo.end(),0);
	}
	int find(int x){
		return bo[x]==x?x:bo[x]=find(bo[x]);
	}
	void merge(int x,int y){
		x=find(x);
		y=find(y);
		bo[x]=y;
	}
}dsu,dsu2;
int construct(vector<vector<int> > p) {
	int n=p.size();
	dsu.init(n);
	dsu2.init(n);
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]){
				dsu.merge(i,j);
			}
			if(p[i][j]==3){
				return 0;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if((p[i][j]>0) + (dsu.find(i)==dsu.find(j))==1){
				return 0;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]==1){
				dsu2.merge(i,j);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]){
				if((p[i][j]==1) + (dsu2.find(i)==dsu2.find(j))==1){
					return 0;
				}
			}	
		}
	}
	vector<int> val(n);
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(dsu.find(i)==dsu.find(j)){
				if(dsu2.find(i)!=dsu2.find(j)){
					if(val[dsu.find(i)] && val[dsu.find(i)]!=p[i][j]){
						return 0;
					}
					val[dsu.find(i)]=p[i][j];
				}
			}
		}
	}
	vector<vector<int> > vx(n);
	vector<vector<int> > bd(n,vector<int>(n));
	for(int i=0;i<n;i++){
		if(i!=dsu2.find(i)){
			bd[i][dsu2.find(i)]=bd[dsu2.find(i)][i]=1;
		}
		else{
			vx[dsu.find(i)].push_back(i);
		}
	}
	for(int i=0;i<n;i++){
		int y=vx[i].size();
		if(y>=3){
			if(val[i]==0){
				return 0;
			}
			if(val[i]==2){
				for(int j=0;j<y;j++){
					bd[vx[i][j]][vx[i][(j+1)%y]]=bd[vx[i][(j+1)%y]][vx[i][j]]=1;
				}
			}
			else if(val[i]==3){
				if(y<=3){
					return 0;
				}
				for(int j=0;j<y;j++){
					bd[vx[i][j]][vx[i][(j+1)%y]]=bd[vx[i][(j+1)%y]][vx[i][j]]=1;
				}
				bd[vx[i][0]][vx[i][2]]=bd[vx[i][2]][vx[i][0]]=1;
			}
		}
		else if(y==2){
			return 0;
		}
	}
	build(bd);
	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