Submission #427211

#	Time	Username	Problem	Language	Result	Execution time	Memory
427211		gonengazit	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	294 ms	24076 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;
	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);
		}
		else{
			edge(from,i);
		}
	}
	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:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0; i+1<cyc.size(); i++){
      |               ~~~^~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:12: warning: unused variable 'j' [-Wunused-variable]
   65 |   for(auto j:conn){
      |            ^

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