Submission #600486

#	Time	Username	Problem	Language	Result	Execution time	Memory
600486		UncoolAnon	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	171 ms	22136 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),gg(n);  
	vector<int> id(n),rid(n),nid(n);  
	for(int i=0;i<n;i++){
		id[i]=i; rid[i]=i; nid[i]=i; 
		group[i].push_back(i);
		grp[i].push_back(i);  
		gg[i].push_back(i); 
	}
	vector<vector<int>> answer(n,vector<int>(n,0)); 


	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&x:grp[i]) if(x!=i) answer[i][x]=answer[x][i]=1; 
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			if(rid[i]!=rid[j]&&rid[i]==i&&rid[j]==j){
				int zero=0,two=0; 
				for(int&x:grp[i])
					for(int&y:grp[j])
						zero+=(p[x][y]==0),two=(p[x][y]==2); 
				if(zero&&two) return 0; 
				if(two){
					merge(i,j,id,group); 
				}
			}
		}
	for(int i=0;i<n;i++)
		if(group[i].size()>1){
			for(int j=0;j<group[i].size();j++)
				answer[group[i][j]][group[i][(j+1)%group[i].size()]]=answer[group[i][(j+1)%group[i].size()]][group[i][j]]=1; 
		}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(answer[i][j]){
				merge(i,j,nid,gg); 
			}
		}
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(p[i][j]==0&&nid[i]!=nid[j]) 
				return 0; 
	build(answer); 
	return 1; 
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:58:17: 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<group[i].size();j++)
      |                ~^~~~~~~~~~~~~~~~

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