Submission #431103

#	Time	Username	Problem	Language	Result	Execution time	Memory
431103		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;
vector<vector<int>>adjans;
int n,vis[N];

void dfs(int i){

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

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

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

	n = p.size();
	adjans = vector<vector<int>>(n,vector<int>(n,0));
	if(n==2)
		return 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.empty()<=1)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;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:42:17: warning: comparison of constant '1' with boolean expression is always true [-Wbool-compare]
   42 |   if(vec.empty()<=1)continue;
      |      ~~~~~~~~~~~^~~
supertrees.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int j=0;j<vec.size();j++)
      |               ~^~~~~~~~~~~
supertrees.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for(int k=j+1;k<vec.size();k++){
      |                  ~^~~~~~~~~~~

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