Submission #431132

#	Time	Username	Problem	Language	Result	Execution time	Memory
431132		Hazem	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	332 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;
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 j=0;j<(int)vec1.size()-1;j++)
				adjans[vec1[j]][vec1[j+1]] = adjans[vec1[j+1]][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;
		if(vec3.size())
			adjans[vec3[0]][vec3.back()] = adjans[vec3.back()][vec3[0]] = 1;
	}

	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:65:15: warning: unused variable 'q' [-Wunused-variable]
   65 |   dfs(i);bool q = 1;
      |               ^
supertrees.cpp:62:7: warning: unused variable 'ans' [-Wunused-variable]
   62 |  bool ans = 1;
      |       ^~~

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