oj.uz

Submission #1083739

# Submission time Handle Problem Language Result Execution time Memory
1083739 2024-09-03T23:25:47 Z rayan_bd Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 440 KB 
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;

vector<int> par(1015),sz(1015,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]+=sz[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 i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(p[i][j]>0) unite(i,j); 
		}
	}

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

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

	for(int i=0;i<n;++i){
		int ulp=findPar(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;
	}

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


	build(adj);
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 440 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 440 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Runtime error 0 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 440 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 440 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -