Submission #1083734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083734		rayan_bd	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	348 KiB

supertrees

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

vector<int> par(1005),sz(1005,1);

int findPar(int u){
	if(par[u]==u) return u;
	return par[u]=findPar(par[u]);
}
void unite(int u,int v){
	int ulp=findPar(u);
	int vlp=findPar(v);
	if(ulp==vlp) return;
	if(sz[ulp]>sz[vlp]){
		par[vlp]=ulp;
		sz[ulp]+=sz[vlp];
	}else{
		par[ulp]=vlp;
		sz[vlp]+=ulp;
	}
}
bool is_samee(int u,int v){
	return findPar(u)==findPar(v);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> adj(n,vector<int>(n,0));

	for(int i=0;i<n;++i){
		par[i]=i;
		for(int j=i+1;j<n;++i){
			if(p[i][j]>0) unite(i,j); 
		}
	}

	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(p[i][j]==0&&is_samee(i,j)){
				return 0;
			}
		}
	}

	vector<vector<int>> compo(n);

	for(int i=0;i<n;++i){
		int ulp=findPar(i);
		if(compo[ulp].size()>=1){
			int u=compo[ulp][compo[ulp].size()-1];
			adj[u][i]=adj[i][u]=1;
		}
		compo[ulp].push_back(i);
	}


	build(adj);
	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