oj.uz

Submission #1083741

# Submission time Handle Problem Language Result Execution time Memory
1083741 2024-09-04T00:24:10 Z rayan_bd Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -