Submission #421545

#	Time	Username	Problem	Language	Result	Execution time	Memory
421545		lakshith_	Connecting Supertrees (IOI20_supertrees)	C++14	19 / 100	281 ms	24004 KiB

supertrees

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

using namespace std;

#define what_is(a) cout<< #a << " is " << a << "\n"
#define checker(a) cout << "checker reached " <<a << "\n"

const int maxn = 1000;

struct subset{
	int parent,rank;
}subsets[maxn];

int find(int a){
	if(subsets[a].parent==a)return a;
	subsets[a].parent = find(subsets[a].parent);
	return subsets[a].parent;
}

void Union(int a,int b){
	a = find(subsets[a].parent),b = find(subsets[b].parent);
	if(a==b)return;
	if(subsets[a].rank<subsets[b].rank)
		subsets[a].parent = b;
	else if(subsets[a].rank>subsets[b].rank)
		subsets[b].parent = a;
	else{
		subsets[a].parent = b;
		subsets[b].rank++;
	}
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	for(int i=0;i<n;i++)subsets[i] = {i,0};
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++){
			if(p[i][j]==0)continue;
			Union(i,j);
		}
		
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			if(p[i][j]==0&&find(i)==find(j)){
				return 0;
			}
			
	vector<vector<int>> sets(n,vector<int>());
	for(int i=0;i<n;i++)
		sets[find(i)].push_back(i);
	vector<vector<int>> g(n,vector<int>());
	for(int i=0;i<n;i++){
		vector<int> vec(n,0);
		g[i] = vec;
	}
	for(vector<int> st : sets){
		if(st.size()==2)return 0;
		if(st.size()<=2)continue;
		for(int i=0;i<(int)st.size()-1;i++)
			g[st[i]][st[i+1]] = g[st[i+1]][st[i]] = 1;
		g[st[0]][st[st.size()-1]] = g[st[st.size()-1]][st[0]] = 1;
	}
	build(g);
	return 1;
}

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