Submission #928012

#	Time	Username	Problem	Language	Result	Execution time	Memory
928012		velislavgarkov	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	175 ms	28244 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e3+10;
vector<vector<int> > ans;
vector <int> v[MAXN], ones, ch, comp[MAXN];
int par[MAXN], d[MAXN];
bool used[MAXN], fl;
int root(int x) {
	if (x==par[x]) return x;
	return par[x]=root(par[x]);
}
void connect(int a, int b) {
	int ra, rb;
	ra=root(a);
	rb=root(b);
	if (ra==rb) return;
	if (d[ra]>d[rb]) par[rb]=ra;
	else if (d[rb]>d[ra]) par[ra]=rb;
	else {
		par[rb]=ra;
		d[ra]++;
	}
}
void find_comp(int x) {
	used[x]=true;
	ch.push_back(x);
	for (auto i:v[x]) {
		if (used[i]) continue;
		find_comp(i);
	}
}
void add_edge(int a, int b) {
	ans[a][b]=ans[b][a]=1;
}
int construct(vector<vector<int> > p) {
	int n = p.size();
	ans.resize(n);
	fl=true;
	for (int i=0;i<n;i++) {
		if (p[i][i]!=1) fl=false;
		for (int j=i+1;j<n;j++) {
			if (p[i][j]==3) fl=false;
			if (p[i][j]) {
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
		par[i]=i;
		d[i]=used[i]=0;
		ans[i].resize(n);
		for (int j=0;j<n;j++) ans[i][j]=0;
	}
	if (!fl) return 0;
	for (int x=0;x<n;x++) {
		if (used[x]) continue;
		if (!ch.empty()) ch.clear();
		find_comp(x);
		if (ch.size()==1) continue;
		for (int i=0;i<ch.size();i++) {
			for (int j=i+1;j<ch.size();j++) {
				if (p[ch[i]][ch[j]]==0) fl=false;
				else if (p[ch[i]][ch[j]]==1) connect(ch[i],ch[j]);
			}
		}
		if (!ones.empty()) ones.clear();
		for (int i=0;i<ch.size();i++) {
			int ri=root(ch[i]);
			if (comp[ri].empty()) ones.push_back(ri);
			comp[ri].push_back(ch[i]);
		}
		for (int i=0;i<ones.size();i++) {
			int nxt=(i-1+ones.size())%ones.size();
			if (nxt!=i) add_edge(ones[i],ones[nxt]);
			int cur=ones[i];
			for (int j=0;j<comp[cur].size();j++) {
				if (j>0) add_edge(comp[cur][j-1],comp[cur][j]);
				for (int k=1;k<comp[cur].size();k++) {
					if (p[comp[cur][j]][comp[cur][j]]==2) fl=false;
				}
			}
		}
	}
	if (!fl) return 0;
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int i=0;i<ch.size();i++) {
      |                ~^~~~~~~~~~
supertrees.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for (int j=i+1;j<ch.size();j++) {
      |                   ~^~~~~~~~~~
supertrees.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i=0;i<ch.size();i++) {
      |                ~^~~~~~~~~~
supertrees.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i=0;i<ones.size();i++) {
      |                ~^~~~~~~~~~~~
supertrees.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for (int j=0;j<comp[cur].size();j++) {
      |                 ~^~~~~~~~~~~~~~~~~
supertrees.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int k=1;k<comp[cur].size();k++) {
      |                  ~^~~~~~~~~~~~~~~~~

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