Submission #316005

#	Time	Username	Problem	Language	Result	Execution time	Memory
316005		gurkot	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	252 ms	22264 KiB

supertrees

#include <iostream>
#include "supertrees.h"
#include <vector>
using namespace std;
int tree[1501],comp[1501],mas[1501],mas2[1501];
int n,ntree,ncomp;

int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	
	//cout<<"ok1: let find trees"<<endl;
	for (int i=0; i<n;i++)	 
	 if (tree[i]==0){	  
	 ++ntree;
	 for (int j=0;j<n;j++) {
	  if(p[i][j] == 3) return 0;
	  	  
	  if (i!=j && p[i][j]==1){
	   if (tree[j]>0) return 0;
	   tree[j]=ntree;	 
	   answer[i][j]=answer[j][i]=1;
      }	
     }//J
	}//i
	
	//cout<<"ok2: let find connected components"<<endl;
	for (int i=0; i<n;i++)	 
	 if (comp[i]==0){	  	  
	  ncomp++;	  
	  int s=i,a=i,k=1,cnt=0;  
	  for (int j=0;j<n;j++)
	   if (i!=j && p[i][j]>0){	   	
	    mas[++cnt]=j;
	    for (int ic=1;ic<cnt;ic++)
	     if (p[mas[ic]] [j]==0 || p[j] [mas[ic]]==0) return 0;
	     
	   	if (comp[j]>0) return 0;
	    comp[j]=ncomp;
	    if (tree[j]==0) {
	      mas2[++k]=j;
	      for (int ic=1;ic<k;ic++)
	      if (p[mas2[ic]] [j]==1 || p[j] [mas2[ic]]==1) return 0;
		  answer[a][j]=answer[j][a]=1;	      
	      a=j;
		}
	   }//j
	   if (k==2) return 0;
	   if (k>2) answer[a][s]=answer[s][a]=1;
	   
	   
	   
	 }//i
	
	
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:37:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   37 |    for (int j=0;j<n;j++)
      |    ^~~
supertrees.cpp:53:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |     if (k==2) return 0;
      |     ^~

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