Submission #431531

#	Time	Username	Problem	Language	Result	Execution time	Memory
431531		Hazem	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	886 ms	34220 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));
 
	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);
			}
		}
 
	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(int k=j+1;k<vec.size();k++)
			for(auto x:vecs[j])
				for(auto y:vecs[k])
					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:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for(int i=0;i<vec1.size();i++)
      |                ~^~~~~~~~~~~~
supertrees.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int j=i+1;j<vec1.size();j++)
      |                   ~^~~~~~~~~~~~
supertrees.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(int k=j+1;k<vec.size();k++)
      |                  ~^~~~~~~~~~~

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