Submission #302693

#	Time	Username	Problem	Language	Result	Execution time	Memory
302693		JooDdae	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	256 ms	22264 KiB

supertrees

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

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++){
			ans[v[i][j]][v[i][(j+1)%sz]] = ans[v[i][(j+1)%sz]][v[i][j]] = 1;
		}
	}

	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int j=0;j<v[i].size()-1;j++){
      |               ~^~~~~~~~~~~~~~
supertrees.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<v2.size();i++) par[i] = i, v[i].clear();
      |              ~^~~~~~~~~~
supertrees.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  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:44:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  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:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<v2.size();i++) v[find(i)].push_back(v2[i]);
      |              ~^~~~~~~~~~
supertrees.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0;i<v2.size();i++) if(v[i].size() > 1){
      |              ~^~~~~~~~~~
supertrees.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int j=0;j<v[i].size();j++){
      |               ~^~~~~~~~~~~~

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