Submission #300641

#	Time	Username	Problem	Language	Result	Execution time	Memory
300641		nandonathaniel	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	264 ms	24040 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
const int MAXN=1005;

int par[MAXN];
bool idx[MAXN];
vector<int> kel[MAXN],kelkecil[MAXN];

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

void join(int a,int b){
	int ortua=find(a),ortub=find(b);
	par[ortua]=ortub;
}

int construct(vector<vector<int>> p){
	vector<pii> nol;
	vector<vector<int>> ans;
	int n = p.size();
	for(int i=0;i<n;i++)par[i]=i;
	ans.resize(n);
	for(int i=0;i<n;i++){
		ans[i].resize(n);
		for(int j=0;j<n;j++){
			ans[i][j]=0;
			if(i==j)continue;
			if(p[i][j])join(i,j);
			else if(i<j)nol.push_back({i,j});
		}
	}
	for(auto isi : nol){
		if(find(isi.first)==find(isi.second))return 0;
	}
	for(int i=0;i<n;i++)kel[find(i)].push_back(i);
	for(int i=0;i<n;i++){
		if(kel[i].size()<=1)continue;
		for(int j=0;j<n;j++){
			kelkecil[j].clear();
			par[j]=j;
			idx[j]=false;
		}
		for(auto isi : kel[i]){
			for(auto isi2 : kel[i]){
				if(p[isi][isi2]==1)join(isi,isi2);
			}
		}
		for(auto isi : kel[i])kelkecil[find(isi)].push_back(isi);
		vector<int> satu1,satu2,dua;
		for(int j=0;j<n;j++){
			if(kelkecil[j].size()<=1)continue;
			if(satu1.empty()){
				satu1=kelkecil[j];
			}
			else{
				if(satu2.empty())satu2=kelkecil[j];
				else return 0;
			}
		}
		if(satu1.empty() && satu2.empty()){
			if(kel[i].size()==2)return 0;
			for(int j=0;j<kel[i].size()-1;j++){
				ans[kel[i][j]][kel[i][j+1]]=1;
				ans[kel[i][j+1]][kel[i][j]]=1;
			}
			continue;
		}
		for(auto isi : satu1)idx[isi]=true;
		for(auto isi : satu2)idx[isi]=true;
		for(auto isi : kel[i]){
			if(!idx[isi])dua.push_back(isi);
		}
		if(!satu1.empty() && !satu2.empty()){
			if(dua.empty())return 0;
			for(int j=0;j<satu1.size()-1;j++){
				ans[satu1[j]][satu1[j+1]]=1;
				ans[satu1[j+1]][satu1[j]]=1;
			}
			ans[satu1.back()][dua[0]]=1;
			ans[dua[0]][satu1.back()]=1;
			for(int j=0;j<(int)dua.size()-1;j++){
				ans[dua[j]][dua[j+1]]=1;
				ans[dua[j+1]][dua[j]]=1;
			}
			ans[dua.back()][satu2[0]]=1;
			ans[satu2[0]][dua.back()]=1;
			for(int j=0;j<satu2.size()-1;j++){
				ans[satu2[j]][satu2[j+1]]=1;
				ans[satu2[j+1]][satu2[j]]=1;
			}
			ans[satu1.back()][satu2[0]]=1;
			ans[satu2[0]][satu1.back()]=1;
		}
		else{
			if(dua.size()==1)return 0;
			for(int j=0;j<satu1.size()-1;j++){
				ans[satu1[j]][satu1[j+1]]=1;
				ans[satu1[j+1]][satu1[j]]=1;
			}
			for(int j=0;j<(int)dua.size()-1;j++){
				ans[dua[j]][dua[j+1]]=1;
				ans[dua[j+1]][dua[j]]=1;
			}
			if(!dua.empty()){
				ans[dua.back()][satu1[0]]=1;
				ans[satu1[0]][dua.back()]=1;
				ans[dua[0]][satu1[0]]=1;
				ans[satu1[0]][dua[0]]=1;
			}
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int j=0;j<kel[i].size()-1;j++){
      |                ~^~~~~~~~~~~~~~~~
supertrees.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(int j=0;j<satu1.size()-1;j++){
      |                ~^~~~~~~~~~~~~~~
supertrees.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    for(int j=0;j<satu2.size()-1;j++){
      |                ~^~~~~~~~~~~~~~~
supertrees.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for(int j=0;j<satu1.size()-1;j++){
      |                ~^~~~~~~~~~~~~~~

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