Submission #302700

#	Time	Username	Problem	Language	Result	Execution time	Memory
302700		JooDdae	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	272 ms	22396 KiB

supertrees

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

// void build(vector<vector<int>> v){
// 	for(auto x : v){
// 		for(int y : x) printf("%d ",y);
// 		printf("\n");
// 	}
// }

int par[1000];
vector<int> v[1000];

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

void merge(int a, int b){
	a = find(a), b = find(b);
	par[a] = 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++) for(int j=i+1;j<n;j++) if(p[i][j] == 3) return 0;

	for(int i=0;i<n;i++) par[i] = i;
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j] == 1) merge(i, j);
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j] != 1 && find(i) == find(j)) return 0;

	for(int i=0;i<n;i++) v[find(i)].push_back(i);
	for(int i=0;i<n;i++) if(v[i].size() > 1){
		for(int j=0;j<v[i].size()-1;j++){
			for(int k=0;k<n;k++){
				if(k != v[i][j] && k != v[i][j+1] && p[v[i][j]][k] != p[v[i][j+1]][k]) return 0;
			}
			ans[v[i][j]][v[i][j+1]] = ans[v[i][j+1]][v[i][j]] = 1;
		}
	}
	
	vector<int> v2;
	for(int i=0;i<n;i++) if(v[i].size()) v2.push_back(v[i][0]);

	for(int i=0;i<v2.size();i++) par[i] = i, v[i].clear();

	for(int i=0;i<v2.size();i++) for(int j=i+1;j<v2.size();j++) if(p[v2[i]][v2[j]] == 2) merge(i, j);

	for(int i=0;i<v2.size();i++) v[find(i)].push_back(v2[i]);

	for(int i=0;i<v2.size();i++) if(v[i].size() > 1){
		if(v[i].size() == 2) return 0;
		int sz = v[i].size();
		for(int j=0;j<v[i].size();j++){
			for(int k=0;k<v[i].size();k++){
				if(j != k && (j+1)%sz != k && (p[v[i][j]][v[i][k]] == 2) != (p[v[i][(j+1)%sz]][v[i][k]] == 2)) return 0;
			}
			ans[v[i][j]][v[i][(j+1)%sz]] = ans[v[i][(j+1)%sz]][v[i][j]] = 1;
		}
	}

	build(ans);
	return 1;
}


// int main(){
// 	int n; scanf("%d",&n);
// 	vector<vector<int>> v(n, vector<int>(n));
// 	for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&v[i][j]);
// 	printf("%d\n",construct(v));
// }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int j=0;j<v[i].size()-1;j++){
      |               ~^~~~~~~~~~~~~~
supertrees.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<v2.size();i++) par[i] = i, v[i].clear();
      |              ~^~~~~~~~~~
supertrees.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<v2.size();i++) for(int j=i+1;j<v2.size();j++) if(p[v2[i]][v2[j]] == 2) merge(i, j);
      |              ~^~~~~~~~~~
supertrees.cpp:51:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<v2.size();i++) for(int j=i+1;j<v2.size();j++) if(p[v2[i]][v2[j]] == 2) merge(i, j);
      |                                             ~^~~~~~~~~~
supertrees.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i=0;i<v2.size();i++) v[find(i)].push_back(v2[i]);
      |              ~^~~~~~~~~~
supertrees.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0;i<v2.size();i++) if(v[i].size() > 1){
      |              ~^~~~~~~~~~
supertrees.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0;j<v[i].size();j++){
      |               ~^~~~~~~~~~~~
supertrees.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int k=0;k<v[i].size();k++){
      |                ~^~~~~~~~~~~~

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