Submission #427200

#	Time	Username	Problem	Language	Result	Execution time	Memory
427200		gonengazit	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	224 ms	23876 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) {
	//return 0;
	// 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:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i=1; i<P.size(); i++){
      |               ~^~~~~~~~~

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