Submission #315654

#	Time	Username	Problem	Language	Result	Execution time	Memory
315654		katearima	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	261 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int i,j,f[2000],z[2000];
vector <vector<int> > tr;
vector <int> v;

int construct(vector<vector<int> > p) {
	
	int n = p.size();
    vector<vector<int> > ans;
	for(i=0; i<n; i++) v.push_back(0);
	for(i=0; i<n; i++) ans.push_back(v);
	v.clear();
	bool possible=true;
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			if(p[i][j]!=p[j][i]) possible=false;
			if(p[i][j]==3) possible=false;
		}
	}
	for(i=0; i<n; i++) f[i]=0;
	for(i=0; i<n; i++){
		bool g=false;
		if(f[i]!=1){
			for(j=0; j<n; j++){
				if(p[i][j]==1) {
					if(f[j]==1){
						possible=false;
						break;
					}
					v.push_back(j);
					f[j]=1;
				}
				if(p[i][j]==2) g=true;
			}
			if(g) v.push_back(1);
			else v.push_back(0);
			tr.push_back(v);
			v.clear();
		}	
	}
	int mn=2000;
	int mx=0;
	//cout<<"------------------------------------------------"<<endl;
	if(possible){
		bool MM=false;
		int N=tr.size();
		for(i=0; i<N; i++){
			for(j=0; j<tr[i].size()-2; j++){
				ans[tr[i][j]][tr[i][j+1]]=1;
				ans[tr[i][j+1]][tr[i][j]]=1;			
			}
			if(tr[i][tr[i].size()-1]==1) {
				mn=min(mn,i); mx=max(mx,i);
				MM=true;
			}
		}
		for(i=0; i<N-1; i++){
			int k=i;
			if(tr[i][tr[i].size()-1]!=0){
				while(tr[i+1][tr[i+1].size()-1]!=1 && i<N-2){
					i++;
				}
				if(tr[i+1][tr[i+1].size()-1]==1){
					ans[tr[k][0]][tr[i+1][0]]=1;
					ans[tr[i+1][0]][tr[k][0]]=1;
				}
			}
		}
		if(MM==true && ans[tr[mx][0]][tr[mn][0]]!=1){
			ans[tr[mx][0]][tr[mn][0]]=1;
			ans[tr[mn][0]][tr[mx][0]]=1;
		}
		else if(MM==true && ans[tr[mx][0]][tr[mn][0]]==1) possible=false;
	}
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			if(p[i][j]==0 && ans[i][j]==1) possible=false;
		}
	}
	
	if(possible) {
		build(ans);
		return 1;
	}
	else return 0;

}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(j=0; j<tr[i].size()-2; 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