Submission #309549

#	Time	Username	Problem	Language	Result	Execution time	Memory
309549		algorithm16	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	279 ms	22392 KiB

supertrees

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include "supertrees.h"
using namespace std;
int parent[1005],d[1005];
vector <vector<int> > sol;
set <int> s1;
vector <int> v1;
int find_par(int x) {
	if(parent[x]==x) return x;
	int par=find_par(parent[x]);
	parent[x]=par;
	return par;
}
void s(int x,int y) {
	if(find_par(x)==find_par(y)) return;
	sol[x][y]=1;
	sol[y][x]=1;
	x=find_par(x);
	y=find_par(y);
	if(x==y) return;
	if(d[x]==d[y]) d[x]+=1;
	if(d[x]>d[y]) parent[y]=x;
	else parent[x]=y;
	s1.insert(x);
	s1.insert(y);
}
int construct(vector <vector<int> > p) {
	int n=p.size(),maxi=0;
	for(int i=0;i<n;i++) {
		parent[i]=i;
		d[i]=1;
		sol.push_back(v1);
		for(int j=0;j<n;j++) {
			sol[i].push_back(0);
		}
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(i==j) continue;
			if(p[i][j]==1) s(i,j);
			maxi=max(maxi,p[i][j]);
		}
	}
	if(maxi>2) return 0;
	if(n==2 && maxi>1) return 0;
	/*for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			cout << sol[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/
	vector <int> v;
	for(int i=0;i<n;i++) {
		v.clear();
		for(int j=0;j<n;j++) {
			if(p[i][j]==2) v.push_back(j);
		}
		if(v.empty()) continue;
		/*for(int j=0;j<v.size();j++) {
			cout << v[j] << " ";
		}
		cout << "\n";*/
		s(i,v[0]);
		for(int j=0;j<v.size()-1;j++) {
			s(v[j],v[j+1]);
		}
		sol[i][v.back()]=1;
		sol[v.back()][i]=1;
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(i==j) continue;
			if(find_par(i)==find_par(j) && p[i][j]==0) return 0;
		}
	}
	build(sol);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int j=0;j<v.size()-1;j++) {
      |               ~^~~~~~~~~~~

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