Submission #312405

#	Time	Username	Problem	Language	Result	Execution time	Memory
312405		huangqr	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1098 ms	22392 KiB

supertrees

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


int vis[1005];
std::vector<std::vector<int>> answer;

int nnn;


void dfs(int pos,vector<int>vd){
	vd.push_back(pos);
	vis[pos]++;
	for(int i=0;i<nnn;i++){
		if(answer[pos][i]==1){
			for(auto x:vd)if(x==i)goto br;
			dfs(i,vd);
		}
		br:;
	}
}

int construct(std::vector<std::vector<int>> p) {
	using namespace std;
	int n=p.size();
	nnn=n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)if(p[i][j]==3||p[j][i]!=p[i][j])return 0;
	}
	int group[1005],small[1005],ctr=-1,ctr2=-1;;
	vector<set<int> >groups,smalls;
	unordered_map<int,vector<int> >groupstosmalls;
	for(int i=0;i<n;i++)group[i]=small[i]=-1;
	for(int i=0;i<n;i++){
		if(p[i][i]!=1)return 0;
		vector<int>r=p[i];
		if(group[i]==-1){
			group[i]=++ctr;
			set<int>cgp={i};
			for(int j=0;j<n;j++){
				if(j==i)continue;
				if(r[j]){
					if(group[j]!=-1)return 0;
					group[j]=ctr;
					cgp.insert(j);
				}
			}
			groups.push_back(cgp);
		}
		else{
			int g=group[i];
			for(int j=0;j<n;j++){
				if(group[j]==g&&r[j]==0)return 0;
				if(group[j]!=g&&r[j])return 0;
			}
		}
		if(small[i]==-1){
			small[i]=i;
			groupstosmalls[group[i]].push_back(i);
			set<int>cgp={i};
			for(int j=0;j<n;j++){
				if(j==i)continue;
				if(r[j]==1){
					if(small[j]!=-1)return 0;
					small[j]=i;
					cgp.insert(j);
				}
			}
			smalls.push_back(cgp);
		}
		else{
			int g=small[i];
			for(int j=0;j<n;j++){
				if(small[j]==g&&r[j]!=1)return 0;
				if(small[j]!=g&&r[j]==1)return 0;
			}
		}
	}
	ctr++;
/*	cout<<"Groups\n";
	for(auto x:groups){
		for(auto y:x){
			cout<<y<<" ";
		}
		cout<<"\n";
	}
	cout<<"Smalls\n";
	for(auto x:smalls){
		for(auto y:x){
			cout<<y<<" ";
		}
		cout<<"\n";
	}
	cout<<"g2s\n";
	for(auto x:groupstosmalls){
		cout<<x.first<<": ";
		for(auto y:x.second)cout<<y<<" ";
		cout<<"\n";
	}
	cout<<"small_val\n";
	for(int i=0;i<n;i++)cout<<small[i]<<" ";
	cout<<"\n";*/
	
	//Set up the empty answer
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		for(int j=0;j<n;j++)row.push_back(0);
		answer.push_back(row);
	}
	
	for(auto x:smalls){
		auto y=++x.begin(),yy=x.begin();
		while(y!=x.end()){
			answer[*y][*yy]=answer[*yy][*y]=1;
			y++,yy++;
		}
	}
	
	for(auto x:groupstosmalls){
		for(int i=0;i<x.second.size()-1;i++){
			answer[x.second[i]][x.second[i+1]]=answer[x.second[i+1]][x.second[i]]=1;
		}
		if(x.second.size()-1)answer[x.second[0]][x.second[x.second.size()-1]]=answer[x.second[x.second.size()-1]][x.second[0]]=1;
	}
	
/*	auto y=++groups.begin(),yy=groups.begin();
	auto aa=yy->begin(),bb=groups.back().begin();
	answer[*aa][*bb]=answer[*bb][*aa]=1;
	while(y!=groups.end()){
		auto aa=yy->begin(),bb=y->begin();
		answer[*aa][*bb]=answer[*bb][*aa]=1;
		y++,yy++;
	}*/
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)vis[j]=0;
		dfs(i,vector<int>());
		for(int j=0;j<n;j++)if(vis[j]!=p[i][j])return 0;
	}
	
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for(int i=0;i<x.second.size()-1;i++){
      |               ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:31:37: warning: unused variable 'ctr2' [-Wunused-variable]
   31 |  int group[1005],small[1005],ctr=-1,ctr2=-1;;
      |                                     ^~~~

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