Submission #309555

#	Time	Username	Problem	Language	Result	Execution time	Memory
309555		algorithm16	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	275 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;
}
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();
		int last=i;
		for(int j=0;j<n;j++) {
			if(p[i][j]==2) {
				if(find_par(i)==find_par(j)) continue;
				s(last,j);
				last=j;
				v.push_back(j);
			}
		}
		if(v.empty()) continue;
		if(v.size()==1) return 0;
		/*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]);
		}*/
		if(s1.find(find_par(i))!=s1.end()) continue;
		s1.insert(find_par(i));
		sol[i][last]=1;
		sol[last][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;
}

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