Submission #715742

#	Time	Username	Problem	Language	Result	Execution time	Memory
715742		n1k	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	190 ms	28040 KiB

supertrees

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

using namespace std;

#define sz(a) (a).size()

vector<vector<int>> components;
vector<bool> vis;
std::vector<std::vector<int>> adj;
int n;

bool dfs(int u){
	vis[u] = 1;
	// u connectet to all in component
	for(auto v : components[sz(components) - 1]){
		if(!adj[v][u]){
			return false;
		}
	}
	components[sz(components) - 1].push_back(u);
	for(int v = 0; v < n; v++){
		if(vis[v]){
			continue;
		}
		if(adj[u][v]){
			if(!dfs(v)){
				return false;
			}
		}
	}
	return true;
}

int construct(std::vector<std::vector<int>> p) {
	adj = p;
	n = p.size();
	vis.resize(n);

	// p[i][j] = 1 -> same component
	// p[j][k] = 1 -> p[i][k] = 1
	// add j
	// j -> has connection to all in component
	// dfs -> j
	
	for(int u = 0; u < n; u++){
		if(vis[u]){
			continue;
		}
		components.push_back(vector<int>());
		if(!dfs(u)){
			return 0;
		}
	}

	vector<vector<int>> mat(n, vector<int>(n));	
	for(auto comp : components){
		for(int i = 0; i < sz(comp) - 1; i++){
			mat[comp[i]][comp[i + 1]] = 1;
			mat[comp[i + 1]][comp[i]] = 1;
		}
	}

	build(mat);

	return 1;
}

Compilation message (stderr)

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

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