Submission #1083741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083741		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> par1(1001),sz1(1001,1),par2(1001),sz2(1001,2);

int findPar1(int u){
	if(par1[u]==u) return u;
	return par1[u]=findPar1(par1[u]);
}

int findPar2(int u){
	if(par2[u]==u) return u;
	return par2[u]=findPar2(par2[u]);
}

void unite1(int u,int v){
	int ulp=findPar1(u);
	int vlp=findPar1(v);
	if(ulp==vlp) return;
	if(sz1[ulp]>sz1[vlp]){
		par1[vlp]=ulp;
		sz1[ulp]+=sz1[vlp];
	}else{
		par1[ulp]=vlp;
		sz1[vlp]+=sz1[ulp];
	}
}

void unite2(int u,int v){
	int ulp=findPar2(u);
	int vlp=findPar2(v);
	if(ulp==vlp) return;
	if(sz2[ulp]>sz2[vlp]){
		par2[vlp]=ulp;
		sz2[ulp]+=sz2[vlp];
	}else{
		par2[ulp]=vlp;
		sz2[vlp]+=sz2[ulp];
	}
}

bool is_samee1(int u,int v){
	return findPar1(u)==findPar1(v);
}

bool is_samee2(int u,int v){
	return findPar2(u)==findPar2(v);
}






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

	// subtask 4

	for(int i=0;i<n;++i) par1[i]=par2[i]=i;

	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(p[i][j]==1){
				unite1(i,j);
			}else if(p[i][j]==2){
				unite2(i,j);
			}
		}
	}

	vector<int> last(n+1,-1),first(n+1,-1),last2(n+1,-1);

	for(int i=0;i<n;++i){
		int ulp=findPar2(i);
		if(last[ulp]!=-1){
			adj[i][last[ulp]]=1;
			adj[last[ulp]][i]=1;
		}
		if(first[ulp]==-1) first[ulp]=i;
		last[ulp]=i;



		int ulp2=findPar1(i);
		if(last2[ulp2]!=-1&&!is_samee1(ulp,ulp2)){
			unite2(ulp,ulp2);
			adj[i][last2[ulp]]=1;
			adj[last2[ulp]][i]=1;
		}
		last2[ulp2]=i;
	}

	for(int i=0;i<n;++i){
		int ulp=findPar2(i);
		if(sz2[ulp]>1) adj[last[ulp]][first[ulp]]=adj[first[ulp]][last[ulp]]=1;
	}



	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