Submission #300518

#	Time	Username	Problem	Language	Result	Execution time	Memory
300518		nandonathaniel	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	268 ms	24164 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];

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;
		vector<int> satu,dua;
		for(int j=0;j<kel[i].size();j++){
			bool ada=false;
			for(int k=0;k<kel[i].size();k++){
				if(j==k)continue;
				if(p[kel[i][j]][kel[i][k]]==1){
					satu.push_back(kel[i][k]);
					ada=true;
				}
			}
			if(ada){
				satu.push_back(kel[i][j]);
				break;
			}
		}
		for(auto isi : satu)idx[isi]=true;
		for(int j=0;j<satu.size();j++){
			for(int k=0;k<kel[i].size();k++){
				if(satu[j]==kel[i][k])continue;
				if(p[satu[j]][kel[i][k]]==1){
					if(!idx[kel[i][k]])return 0;
				}
			}
		}
		for(auto isi : kel[i]){
			if(!idx[isi])dua.push_back(isi);
		}
		if(!satu.empty()){
			dua.push_back(satu.back());
			satu.pop_back();
		}
		if(dua.size()==2)return 0;
		for(int i=0;i<dua.size();i++){
			for(int j=0;j<dua.size();j++){
				if(i==j)continue;
				if(p[dua[i]][dua[j]]!=2)return 0;
			}
		}
		for(int i=0;i<(int)dua.size()-1;i++){
			ans[dua[i]][dua[i+1]]=1;
			ans[dua[i+1]][dua[i]]=1;
		}
		if(!dua.empty() && dua.size()>1){
			ans[dua[0]][dua.back()]=1;
			ans[dua.back()][dua[0]]=1;
		}
		if(!satu.empty() && !dua.empty()){
			ans[dua.back()][satu[0]]=1;
			ans[satu[0]][dua.back()]=1;
		}
		for(int i=0;i<(int)satu.size()-1;i++){
			ans[satu[i]][satu[i+1]]=1;
			ans[satu[i+1]][satu[i]]=1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:43:16: 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<kel[i].size();j++){
      |               ~^~~~~~~~~~~~~~
supertrees.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for(int k=0;k<kel[i].size();k++){
      |                ~^~~~~~~~~~~~~~
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<satu.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<kel[i].size();k++){
      |                ~^~~~~~~~~~~~~~
supertrees.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i=0;i<dua.size();i++){
      |               ~^~~~~~~~~~~
supertrees.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(int j=0;j<dua.size();j++){
      |                ~^~~~~~~~~~~

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