Submission #1291721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291721		enzy	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	108 ms	27456 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int pai[maxn];
vector<int>cmp[maxn], vontade[maxn];
int find(int a){
	if(a==pai[a]) return a;
	return pai[a]=find(pai[a]);
}
void merge(int a, int b){
	a=find(a); b=find(b);
	if(a==b) return;
	if(cmp[a]<cmp[b]) swap(a,b);
	for(int x : cmp[b]) cmp[a].push_back(x);
	for(int x : vontade[b]) vontade[a].push_back(x);
	pai[b]=a;
	cmp[b].clear();
	vontade[b].clear();
}
int construct(vector<vector<int>> p){
	int n=p.size();
	for(int i=0;i<n;i++){
		pai[i]=i;
		cmp[i].push_back(i);
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) if(p[i][j]==1) merge(i,j);
	//cout << "obvio" << endl;
	// juntei tds os caras q formarão as árvoes
	vector<vector<int>>ans(n,vector<int>(n,0));
	for(int i=0;i<n;i++){
		int last=-1;
		for(int x : cmp[i]){
			if(last!=-1) ans[x][last]=ans[last][x]=1;
			for(int y : cmp[i]) if(x!=y&&p[x][y]!=1) return 0;
			last=x;
		}
		for(int x : cmp[i]) vontade[i].push_back(x);
		cmp[i].clear();
		cmp[i].push_back(i);
	}
	//cout << "eh" << endl;
	// chequei se não tinha incongruencias
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			if(p[i][j]==2){
				int a=find(i), b=find(j);
				if(a==b) continue;
				for(int x : vontade[a])
					for(int y : vontade[b]) if(x!=y&&p[x][y]!=2) return 0;
				merge(a,b);
			}
		}
	//cout << "wow" << endl;
	for(int i=0;i<n;i++){
		if(cmp[i].size()==2) return 0;
		if(cmp[i].size()<=2) continue;
		int first=cmp[i][0], last=-1;
		for(int x : cmp[i]){
			if(last!=-1) ans[x][last]=ans[last][x]=1;
			last=x;
		}
		ans[last][first]=ans[first][last]=1;
	}
	//cout << "ah n" << endl;
	build(ans);
	return 1;
}

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