Submission #600450

#	Time	Username	Problem	Language	Result	Execution time	Memory
600450		UncoolAnon	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	212 KiB

supertrees

#include <bits/stdc++.h> 
#include "supertrees.h"
using namespace std; 
const int inf=1e9; 
void merge(int i,int j,vector<int>& id,vector<vector<int>>& group){
	if(id[i]!=id[j]){
		int a=id[i],b=id[j]; 
		if(group[a].size()>group[b].size()) swap(a,b); 
		for(int&x:group[a]) group[b].push_back(x); 
		for(int&x:group[a]) id[x]=b; 
		group[a].clear(); 
	}	
	return ; 
}
int construct(vector<vector<int>> p){
	int n=p.size(); 
	vector<vector<int>> group(n),grp(n); 
	vector<int> id(n),rid(n); 
	for(int i=0;i<n;i++){
		id[i]=i; rid[i]=i; 
		group[i].push_back(i);
		grp[i].push_back(i);  
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j){
				if(p[i][j]==2)
					merge(i,j,id,group); 
			}
		}
	} 
	vector<vector<int>> answer(n,vector<int>(n,0)); 
	for(int i=0;i<n;i++){
		for(int&x:group[i]){
			for(int&y:group[i])
				if(x!=y&&p[x][y]!=2){
					return 0; 
				}
		}
		for(int j=0;j+1<group[i].size();j++) answer[group[i][j]][group[i][j+1]]=answer[group[i][j+1]][group[i][j]]=1; 
	}

	/*for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j&&group[id[i]].size()==1&&group[id[j]].size()==1&&p[i][j]==1){
				merge(i,j,rid,grp);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int&x:grp[i])
			for(int&y:grp[i])
				if(p[x][y]!=1)
					return 0; 
	}
	for(int i=0;i<n;i++){
		for(int j=0;j+1<grp[i].size();j++)
			answer[grp[i][j]][grp[i][j+1]]=answer[grp[i][j]][grp[i][j+1]]=1;
	}
	vector<int> cnt(n); 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(group[id[i]].size()==1&&group[id[j]].size()==2&&p[i][j]==1){
				if(cnt[rid[i]]) return 0; 
				cnt[rid[i]]=1; 
				answer[rid[i]][id[j]]=answer[id[j]][rid[i]]=1; 
				for(int&x:grp[rid[i]])
					for(int&y:group[id[j]])
						if(p[x][y]==0)
							return 0; 
			}	
		}
	}*/
	build(answer); 
	return 1; 
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j=0;j+1<group[i].size();j++) answer[group[i][j]][group[i][j+1]]=answer[group[i][j+1]][group[i][j]]=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