Submission #431282

#	Time	Username	Problem	Language	Result	Execution time	Memory
431282		Hazem	Connecting Supertrees (IOI20_supertrees)	C++14	75 / 100	358 ms	34172 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3+10;

vector<int>adj[N],vec,vec1;
vector<vector<int>>adjans,p,vecs;
int n,vis[N],vis1[N];

void dfs(int i){

	if(vis[i])
		return ;
	vis[i] = 1;
	vec.push_back(i);

	for(auto x:adj[i])
		dfs(x);
}

void dfs(int i,int t){

	if(vis1[i])
		return ;

	vis1[i] = 1;
	vec1.push_back(i);
	for(auto x:adj[i])
		if(p[i][x]==1)
			dfs(x,t);
}

bool checkallequal(vector<int>vec1){

	bool ret = 1;
	for(int i=0;i<vec.size();i++)
		for(int j=i+1;j<vec.size();j++){
			bool q = 0;
			for(auto x:vec1)
				q |= p[vec[i]][vec[j]]==x;
			ret &= q;
		}
	return ret;
}

int construct(std::vector<std::vector<int>> P) {

	p = P;
	n = p.size();
	adjans = vector<vector<int>>(n,vector<int>(n,0));

	int mx = 0,mn = 10;set<int>st;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			if(p[i][j]){
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
			if(i!=j){
				mn = min(mn,p[i][j]);
				mx = max(mx,p[i][j]);
				st.insert(p[i][j]);
			}
		}

	if(mx<=1){
		bool ans = 1;
	for(int i=0;i<n;i++){
		
		dfs(i);bool q = 1;
		for(int j=0;j<vec.size();j++)
			for(int k=0;k<vec.size();k++)
				q &= p[vec[j]][vec[k]]==1;
 
		//q &= !vec.size()||vec.size()>2;
		for(int j=0;j<(int)vec.size()-1;j++)
			adjans[vec[j]][vec[j+1]] = adjans[vec[j+1]][vec[j]] = 1;
 
		//adjans[vec[0]][vec.back()] = adjans[vec.back()][vec[0]] = 1;
		vec.clear();
		ans &= q;
	}

	if(!ans)
		return 0;
 
	build(adjans);
	return 1;

	}

	if((mx==mn)||(!mn&&st.size()==2)){
		bool ans = 1;
	for(int i=0;i<n;i++){
		
		dfs(i);bool q = 1;
		if(vec.size()<=1){
			vec.clear();
			continue;
		}
 
		for(int j=0;j<vec.size();j++)
			for(int k=j+1;k<vec.size();k++){
				q &= p[vec[j]][vec[k]]==2;
				assert(vec[j]!=vec[k]);
			}
			
 
		q &= vec.size()>2;
		for(int j=0;j<(int)vec.size()-1;j++)
			adjans[vec[j]][vec[j+1]] = adjans[vec[j+1]][vec[j]] = 1;
		
		adjans[vec[0]][vec.back()] = adjans[vec.back()][vec[0]] = 1;
		vec.clear();
		ans &= q;
	}
 
	if(!ans)
		return 0;
 
	build(adjans);
	return 1;

	}

	bool ans = 1;
	for(int i=0;i<n;i++){
		
		dfs(i);bool q = 1;
		if(vec.size()<=1){
			vec.clear();
			continue;
		}

		vector<int>vec3;
		for(auto x:vec){
			
			dfs(x,1);
			for(int i=0;i<vec1.size();i++)
				for(int j=i+1;j<vec1.size();j++)
					q &= p[vec1[i]][vec1[j]]==1;
			
			vecs.push_back(vec1);
			for(int j=0;j<(int)vec1.size()-1;j++){
				adjans[vec1[j]][vec1[j+1]] = adjans[vec1[j+1]][vec1[j]] = 1;
				assert(vec1[j]!=vec1[j+1]);
			}
			
			if(vec1.size())
				vec3.push_back(x);
			vec1.clear();
		}
		
		for(int j=0;j<(int)vec3.size()-1;j++){
			adjans[vec3[j]][vec3[j+1]] = adjans[vec3[j+1]][vec3[j]] = 1;
			assert(vec3[j]!=vec3[j+1]);
		}

		q &= vec3.size()!=2;
		if(vec3.size()>1){
			adjans[vec3[0]][vec3.back()] = adjans[vec3.back()][vec3[0]] = 1;
			assert(vec[0]!=vec3.back());
		}

		for(int j=0;j<(int)vecs.size()-1;j++)
			for(auto x:vecs[j])
				for(auto y:vecs[j+1])
					q &= p[x][y]==2;
		
		ans &= q;
		vecs.clear();
	}

	if(!ans)
		return 0;

	build(adjans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool checkallequal(std::vector<int>)':
supertrees.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<vec.size();i++)
      |              ~^~~~~~~~~~~
supertrees.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j=i+1;j<vec.size();j++){
      |                 ~^~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j=0;j<vec.size();j++)
      |               ~^~~~~~~~~~~
supertrees.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(int k=0;k<vec.size();k++)
      |                ~^~~~~~~~~~~
supertrees.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int j=0;j<vec.size();j++)
      |               ~^~~~~~~~~~~
supertrees.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    for(int k=j+1;k<vec.size();k++){
      |                  ~^~~~~~~~~~~
supertrees.cpp:142:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |    for(int i=0;i<vec1.size();i++)
      |                ~^~~~~~~~~~~~
supertrees.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int j=i+1;j<vec1.size();j++)
      |                   ~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4