Submission #432095

#	Time	Username	Problem	Language	Result	Execution time	Memory
432095		peuch	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	269 ms	24236 KiB

supertrees

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

const int MAXN = 1010;

int rep[MAXN];
vector<int> grp[MAXN];

int rep2[MAXN];
vector<int> grp2[MAXN];

int find(int a);
void uni(int a, int b);
int find2(int a);
void uni2(int a, int b);

int construct(vector<vector<int> > p) {
	int n = p.size();
	vector<vector<int> > ans (n, vector<int> (n));
	
	for(int i = 0; i < n; i++){
		rep[i] = i;
		grp[i].push_back(i);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 0) continue;
			uni(i, j);
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] != 0) continue;
			if(find(i) == find(j)) return 0;
		}
	}
	
	for(int i = 0; i < n; i++){
		if(i != rep[i]) continue;
		bool flag1 = true;
		for(int j = 0; j < grp[i].size(); j++){
			for(int k = 0; k < grp[i].size(); k++){
				int a = grp[i][j], b = grp[i][k];
				if(p[a][b] == 0) return 0;
				flag1 &= p[a][b] == 1; 
			}
		}
		if(flag1){
			for(int j = 1; j < grp[i].size(); j++){
				int a = grp[i][j], b = grp[i][j - 1];
				ans[a][b] = 1;
				ans[b][a] = 1;
			}
		}
		else{
			vector<int> aux;
			for(int j = 0; j < grp[i].size(); j++){
				int a = grp[i][j];
				rep2[a] = a;
				grp2[a].push_back(a);
			}
			for(int j = 0; j < grp[i].size(); j++){
				for(int k = 0; k < grp[i].size(); k++){
					int a = grp[i][j], b = grp[i][k];
					if(p[a][b] == 2) continue;
					uni2(a, b);
				}
			}
			for(int j = 0; j < grp[i].size(); j++){
				for(int k = 0; k < grp[i].size(); k++){
					int a = grp[i][j], b = grp[i][k];
					if(p[a][b] != 2) continue;
					if(find2(a) == find2(b)) return 0;
				}
			}
			for(int j = 0; j < grp[i].size(); j++){
				int a = grp[i][j];
				if(a != rep2[a]) continue;
				aux.push_back(a);
				for(int k = 0; k < grp2[a].size(); k++){
					for(int l = 0; l < grp2[a].size(); l++){
						int b = grp2[a][k], c = grp2[a][l];
						if(p[a][b] != 1) return 0;
					}
				}
				for(int k = 1; k < grp2[a].size(); k++){
					int b = grp2[a][k], c = grp2[a][k - 1];
					ans[b][c] = 1;
					ans[c][b] = 1;
				}
			}
			if(aux.size() <= 2) return 0;
			for(int j = 1; j < aux.size(); j++){
				int b = aux[j], c = aux[j - 1];
				ans[b][c] = 1;
				ans[c][b] = 1;
			}
			ans[aux[0]][aux.back()] = 1;
			ans[aux.back()][aux[0]] = 1;
		}
	}
	
	build(ans);
	return 1;
}

int find(int a){
	if(a == rep[a]) return a;
	return rep[a] = find(rep[a]);
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	if(grp[a].size() < grp[b].size()) swap(a, b);
	for(int i = 0; i < grp[b].size(); i++)
		grp[a].push_back(grp[b][i]);
	grp[b].clear();
	rep[b] = a;
}

int find2(int a){
	if(a == rep2[a]) return a;
	return rep2[a] = find2(rep2[a]);
}

void uni2(int a, int b){
	a = find2(a);
	b = find2(b);
	if(a == b) return;
	if(grp2[a].size() < grp2[b].size()) swap(a, b);
	for(int i = 0; i < grp2[b].size(); i++)
		grp2[a].push_back(grp2[b][i]);
	grp2[b].clear();
	rep2[b] = a;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j = 0; j < grp[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~
supertrees.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int k = 0; k < grp[i].size(); k++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int j = 1; j < grp[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int j = 0; j < grp[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for(int j = 0; j < grp[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int k = 0; k < grp[i].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~
supertrees.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int j = 0; j < grp[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int k = 0; k < grp[i].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~
supertrees.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(int j = 0; j < grp[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int k = 0; k < grp2[a].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~~
supertrees.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |      for(int l = 0; l < grp2[a].size(); l++){
      |                     ~~^~~~~~~~~~~~~~~~
supertrees.cpp:84:27: warning: unused variable 'c' [-Wunused-variable]
   84 |       int b = grp2[a][k], c = grp2[a][l];
      |                           ^
supertrees.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int k = 1; k < grp2[a].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~~
supertrees.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for(int j = 1; j < aux.size(); j++){
      |                   ~~^~~~~~~~~~~~
supertrees.cpp: In function 'void uni(int, int)':
supertrees.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i = 0; i < grp[b].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~
supertrees.cpp: In function 'void uni2(int, int)':
supertrees.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for(int i = 0; i < grp2[b].size(); 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