Submission #427240

#	Time	Username	Problem	Language	Result	Execution time	Memory
427240		gonengazit	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	273 ms	24052 KiB

supertrees

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

vector<vector<int>> ret;
vector<vector<int>> p;

inline void edge(int i, int j){
	ret[i][j]=ret[j][i]=1;
}
bool create(vector<int> conn){
	vector<int> cyc;
	vector<int> fr(ret.size(),-1);
	for(auto i:conn){
		int from=-1;
		for(auto j:cyc){
			if(p[i][j]==0){
				return false;
			}
			else if(p[i][j]==1){
				if(from!=-1){
					return false;
				}
				else{
					from=j;
				}
			}
		}
		if(from==-1){
			cyc.push_back(i);
			fr[i]=i;
		}
		else{
			edge(from,i);
			fr[i]=from;
		}
	}
	for(auto i:conn){
		for(auto j:conn){
			if(i==j){
				continue;
			}
			if(fr[i]==fr[j]&&p[i][j]!=1||
			(fr[i]!=fr[j]&&p[i][j]!=2)){
				return false;
			}
		}
	}
	for(int i=0; i+1<cyc.size(); i++){
		edge(cyc[i],cyc[i+1]);
	}
	if(cyc.size()==2){
		return false;
	}
	if(cyc.size()>2){
		edge(cyc[0],cyc.back());
	}
	return true;
}
int construct(std::vector<std::vector<int>> P) {
	p=move(P);
	int n=p.size();
	vector<bool> used(n,false);
	ret.assign(n,vector<int>(n,0));
	for(int i=0; i<n; i++){
		if(used[i]){
			continue;
		}
		used[i]=true;
		vector<int> conn;
		conn.push_back(i);
		for(int j=i+1; j<n; j++){
			if(p[i][j]>0){
				conn.push_back(j);
				used[j]=true;
			}
		}
		for(auto j:conn){
			for(int k=0; k<n; k++){
				if(p[i][k]==0&&p[j][k]!=0){
					return 0;
				}
			}
		}
		if(!create(conn)){
			return 0;
		}
	}
	build(ret);
	return 1;

	// vector<vector<int>> v(P.size(),vector<int>(P.size(),0));
	// for(int i=1; i<P.size(); i++){
	// 	v[0][i]=v[i][0]=1;
	// }
	// build(v);
	// return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool create(std::vector<int>)':
supertrees.cpp:44:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   44 |    if(fr[i]==fr[j]&&p[i][j]!=1||
supertrees.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0; i+1<cyc.size(); i++){
      |               ~~~^~~~~~~~~~~

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