Submission #300718

#	Time	Username	Problem	Language	Result	Execution time	Memory
300718		nandonathaniel	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	274 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;
		}
		bool dua=false,tiga=false;
		for(auto isi : kel[i]){
			for(auto isi2 : kel[i]){
				if(p[isi][isi2]==1)join(isi,isi2);
				else if(p[isi][isi2]==3)tiga=true;
				else dua=true;
			}
		}
		if(dua && tiga)return 0;
		for(auto isi : kel[i])kelkecil[find(isi)].push_back(isi);
		vector<vector<int>> satu;
		vector<int> rest;
		for(int j=0;j<n;j++){
			if(kelkecil[j].size()<=1)continue;
			satu.push_back(kelkecil[j]);
		}
		for(auto isi : satu){
			for(auto isi2 : isi)idx[isi2]=true;
		}
		for(auto isi : kel[i]){
			if(!idx[isi])rest.push_back(isi);
		}
		vector<int> cycle;
		for(auto isi : rest)cycle.push_back(isi);
		for(auto isi : satu)cycle.push_back(isi.back());
		if(cycle.size()==2)return 0;
		for(auto isi : satu){
			for(int j=0;j<isi.size()-1;j++){
				ans[isi[j]][isi[j+1]]=1;
				ans[isi[j+1]][isi[j]]=1;
			}
		}
		if(cycle.size()>1){
			for(int j=0;j<cycle.size();j++){
				ans[cycle[j]][cycle[(j+1)%cycle.size()]]=1;
				ans[cycle[(j+1)%cycle.size()]][cycle[j]]=1;
			}
			if(tiga){
				if(cycle.size()==3)return 0;
				else{
					ans[cycle[0]][cycle[2]]=1;
					ans[cycle[2]][cycle[0]]=1;
				}
			}
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int j=0;j<isi.size()-1;j++){
      |                ~^~~~~~~~~~~~~
supertrees.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int j=0;j<cycle.size();j++){
      |                ~^~~~~~~~~~~~~

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