Submission #432455

#	Time	Username	Problem	Language	Result	Execution time	Memory
432455		dreezy	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	324 ms	24084 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++){
			//cout<<i<<", "<<j<<endl;
			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(j);
		}
	}
	
	
	
	vector<vector<int>> ans(n, vector<int>(n, 0));
	
	
	for(auto e : trees){
		set<int> tree = e.second;
		//cout << e.first<<endl;
		vector<vector<int>> graph(tree.size(), vector<int>());
		UnionFind uft;
		uft.init(n);
		vector<int> degree(n, 0);
		int endpoint = -1;
		
		vector<bool> vis(n, 0);
		for(int i : tree){
			for(int j : tree){
				if(i == j) continue;
				//cout << i <<", "<<j<<endl;
				if(p[i][j] ==1){
					if(!uft.same(i, j)){
						vis[i] = vis[j] = true;
						degree[i]++;
						degree[j]++;
						ans[i][j] = ans[j][i] =1;
						uft.join(i, j);
					}
				}
			}
		}
		
		for(int i : tree)
			if(degree[i] == 1){
				endpoint = i;
				break;
			}
	
		int first = -1, last = -1;
		for(int i : tree){
			if(vis[i]) continue;
			for(int j : tree){
				if(vis[j]) continue;
				if(i == j) continue;
				if(p[i][j] >1){
					if(!uft.same(i, j)){
						if(first == -1) first = i;
						last = j;
						ans[i][j] = ans[j][i] = 1;
						uft.join(i, j);
						break;
					}
				}
			}
		}
		
		if(first == -1) continue;
		
		if(endpoint != -1){
			ans[endpoint][first] = ans[first][endpoint] = 1;
			ans[endpoint][last] = ans[last][endpoint] =1;
		}
		else{
			ans[last][first] = ans[first][last] = 1;
		}
		//cout <<endpoint<<endl;
		//cout << first<<", "<<last<<endl;
		
	}
	
	
	build(ans);
	return 1;
}

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