oj.uz

Submission #1083732

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

struct DSU
{
	int N;
	vector<int> par,sz;
	void init(int n){
		N=n;
		par.resize(n+1);
		sz.resize(n+1,1);
		iota(par.begin(),par.end(),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_same(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));
	
	DSU dsu;
	dsu.init(n+1);

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

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

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

	for(int i=0;i<n;++i){
		int ulp=dsu.findPar(i);
		compo[ulp].push_back(i);
	}

	for(int i=0;i<n;++i){
		for(int j=0;j<compo[i].size()-1;++j){
			int u=compo[i][j],v=compo[i][j+1];
			adj[u][v]=adj[v][u]=1;
		}
	}


	build(adj);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int j=0;j<compo[i].size()-1;++j){
      |               ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1144 ms 1728780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1144 ms 1728780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 1700948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1107 ms 1716816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1144 ms 1728780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1144 ms 1728780 KB Time limit exceeded
2 Halted 0 ms 0 KB -