Submission #715752

#	Time	Username	Problem	Language	Result	Execution time	Memory
715752		n1k	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	278 ms	26112 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);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 3){
				return 0;
			}
		}
	}
	// 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;
		}
	}

	vis.assign(n, 0);
	// construckt trees
	vector<vector<int>> mat(n, vector<int>(n));	
	for(auto comp : components){
		vector<int> roots;
		for(auto u : comp){
			if(vis[u]){
				continue;
			}
			roots.push_back(u);
			for(int i = 0; i < n; i++){
				if(u == i){
					continue;
				}
				if(p[u][i] == 1){
					vis[i] = 1;
					mat[u][i] = mat[i][u] = 1;
				}
			}
		}
		if(sz(roots) == 2){
			return 0;
		}else if(sz(roots) > 2){
			for(int i = 0; i < sz(roots); i++){
				mat[roots[i]][roots[(i + 1) % sz(roots)]] = mat[roots[(i + 1) % sz(roots)]][roots[i]] = 1;
			}
		}
	}
 
	build(mat);
 
	return 1;
}

Compilation message (stderr)

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

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