Submission #432442

#	Time	Username	Problem	Language	Result	Execution time	Memory
432442		dreezy	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	204 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3  + 5;
#define pb push_back
struct UnionFind{
	int parent[maxn], height[maxn];
	
	void init(int n){
		for(int i =0; i<n; i++) parent[i] =i;
		memset(height, 0, sizeof height);
	}
	
	int root(int n){
		if(parent[n]!= n)
			parent[n] = root(parent[n]);
		return parent[n];
	}
	
	bool same(int n1, int n2){
		return root(n1) == root(n2);
	}
	
	void join(int n1, int n2){
		int r1 = root(n1);
		int r2 = root(n2);
		
		if(height[r1]> height[r2]){
			parent[r2] = r1;
			height[r1] = max(height[r1]+1, height[r2]);
		}
		else{
			parent[r1] = r2;
			height[r2] = max(height[r2]+1, height[r1]);
			
		}
	}
};


int construct(vector<vector<int>> p) {
	int n = p.size();
	
	UnionFind uf;
	uf.init(n);
	
	for(int i =0; i<n-1 ; i++){
		for(int j = i + 1; j<n; j++){
			if(p[i][j] > 0) uf.join(i, j);
		}
	}
	map<int, set<int>> trees;
	for(int i =0; i<n -1; i++){
		for(int j =i + 1; j< n; j++){
			if(p[i][j] == 0)
				if(uf.same(i, j))return 0;
			trees[uf.root(i)].insert(i);
			trees[uf.root(j)].insert(i);
		}
	}
	
	
	
	vector<vector<int>> ans(n, vector<int>(n, 0));
	
	
	for(auto e : trees){
		set<int> tree = e.second;
		vector<vector<int>> graph(tree.size(), vector<int>());
		UnionFind uft;
		uft.init(n);
		vector<int> degree(n, 0);
		//int endpoint;
		
		
		for(int i : tree){
			for(int j : tree){
				if(p[i][j] ==1){
					if(!uft.same(i, j)){
						degree[i]++;
						degree[j]++;
						ans[i][j] = ans[j][i] =1;
						uf.join(i, j);
					}
				}
			}
		}
		
		
		
	}
	
	
	build(ans);
	return 1;
}

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