Submission #313726

#	Time	Username	Problem	Language	Result	Execution time	Memory
313726		keta_tsimakuridze	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	283 ms	34172 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int par[N],sz[N],a[N][N],ans[N][N],type[N],k,i,n,u,v,x,y,fix[N],cycle[N];
vector<int> comp[N],V[N],E;
vector<vector<int> > answer;
int find_parent(int u){
	if(par[u]==u) return u;
	return par[u]=find_parent(par[u]);
}
void merge(int u,int v){
	u=find_parent(u);
	v=find_parent(v);
	if(u==v) return;
	if(sz[u]<sz[v]) swap(u,v);
	par[v]=u;
	sz[u]+=sz[v];
}
void Go(int u){
	for(k=0;k<comp[u].size();k++){
		for(i=k+1;i<comp[u].size();i++){
			int x=comp[u][k];
			int y=comp[u][i];
			if(a[x][y]==1){
			 V[x].push_back(y);
			 V[y].push_back(x); }
		}
	}
	E.clear();
	for(k=0;k<comp[u].size();k++){
		x=comp[u][k]; 
		if(fix[x]) continue;
		E.push_back(x);
		type[x]=1;
		if(!fix[x]){
			for(i=0;i<V[x].size();i++){
				fix[V[x][i]]=x;
				ans[x][V[x][i]]=ans[V[x][i]][x]=1;
			}
		}
	}
	if(E.size()>1){
		for(k=0;k<E.size();k++){
			ans[E[k]][E[(k+1)%E.size()]]=ans[E[(k+1)%E.size()]][E[k]]=1;
		}
	}
}
bool check(){
	for(k=1;k<=n;k++){
		std::vector<int> row;
		for(i=1;i<=n;i++){

			if(i==k) ans[k][i]=0;
			else {
				int x=find_parent(k);
				int y=find_parent(i);
				if(a[k][i]==0 && x==y)return 0;
				if(!type[k] && !type[i] && a[k][i]==2 && fix[k]==fix[i]) return 0;
			}
			row.push_back(ans[k][i]); 
		}answer.push_back(row);
	}
	return 1;
}
int construct(std::vector<std::vector<int> > v){
	//[[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]]
	n=v.size(); 
	for(k=1;k<=n;k++)
	par[k]=k,sz[k]=1;
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			a[k][i]=v[k-1][i-1];
		//	cout<<a[k][i]<<" ";
			if(a[k][i]==3) {
			return 0;	
			}
			if(a[k][i]!=0) merge(k,i);
		}
	//	cout<<endl;
	}
	for(k=1;k<=n;k++){
		comp[find_parent(k)].push_back(k);
	} 
	for(int k=1;k<=n;k++){
		Go(k);
		if(E.size()==2 && a[E[0]][E[1]]==2) return 0;
	}
	if(!check()) return 0;
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void Go(int)':
supertrees.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(k=0;k<comp[u].size();k++){
      |          ~^~~~~~~~~~~~~~~
supertrees.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(i=k+1;i<comp[u].size();i++){
      |             ~^~~~~~~~~~~~~~~
supertrees.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(k=0;k<comp[u].size();k++){
      |          ~^~~~~~~~~~~~~~~
supertrees.cpp:37:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(i=0;i<V[x].size();i++){
      |            ~^~~~~~~~~~~~
supertrees.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(k=0;k<E.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