Submission #428448

#	Time	Username	Problem	Language	Result	Execution time	Memory
428448		alireza_kaviani	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	270 ms	30120 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
int n , par[MAXN] , sz[MAXN] , mark[MAXN] , adj[MAXN][MAXN] , ans[MAXN][MAXN];
vector<int> vec , comp[MAXN];

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v;
	sz[v] += sz[u];
}

void DFS(int v){
	mark[v] = 1; vec.push_back(v);
	for(int u = 0 ; u < n ; u++){
		if(adj[v][u] > 0 && mark[u] == 0)	DFS(u);
	}
}

int solve(vector<int> v){
	vector<int> vec;
	for(int i : v){
		if(Find(i) == i){
			vec.push_back(i);
		}
	}
	int m = vec.size();
	if(m == 2)	return 0;
	for(int i = 0 ; i < m ; i++){
		int v = vec[i] , u = vec[(i + 1) % m];
		if(v != u)	ans[v][u] = ans[u][v] = 1;
	}
	int flag2 = 0 , flag3 = 0;
	for(int i : v){
		for(int j : v){
			if(adj[i][j] == 2)	flag2 = 1;
			if(adj[i][j] == 3)	flag3 = 1;
		}
	}
	if(flag2 + flag3 == 0)	return 1;
	if(flag2 && flag3)	return 0;
	if(flag2)	return 1;
	if(m <= 3)	return 0;
	ans[vec[0]][vec[2]] = ans[vec[2]][vec[0]] = 1;
	return 1;
}

int construct(vector<vector<int>> p) {
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	n = p.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(n , 0);
		answer.push_back(row);
		for(int j = 0 ; j < n ; j++){
			adj[i][j] = p[i][j];
			if(adj[i][j] == 1)	Union(i , j);
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			if(Find(i) == Find(j) && adj[i][j] != 1)	return 0;
		}
		comp[Find(i)].push_back(i);
	}
	for(int i = 0 ; i < n ; i++){
		if(comp[i].size() == 0)	continue;
		for(int j = 0 ; j + 1 < comp[i].size() ; j++){
			if(comp[i][j] == i){
				swap(comp[i][j] , comp[i][comp[i].size() - 1]);
			}
		}
		for(int j = 0 ; j + 1 < comp[i].size() ; j++){
			int v = comp[i][j] , u = comp[i][j + 1];
			ans[v][u] = ans[u][v] = 1;
		}
	}
	for(int i = 0 ; i < n ; i++){
		if(!mark[i]){
			vec.clear();
			DFS(i);
			for(int j : vec){
				for(int k : vec){
					if(adj[j][k] == 0)	return 0;
				}
			}
			if(solve(vec) == 0)	return 0;
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			answer[i][j] = ans[i][j];
		}
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:77:25: 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 = 0 ; j + 1 < comp[i].size() ; j++){
      |                   ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:82:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int j = 0 ; j + 1 < comp[i].size() ; j++){
      |                   ~~~~~~^~~~~~~~~~~~~~~~

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