Submission #1063268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063268		jamjanek	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	126 ms	22408 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int father1[1010], father[1010], father3[1010];
int find1(int x){
	if(father1[x]==x)return x;
	return father1[x] = find1(father1[x]);
}
int find2(int x){
	if(father[x]==x)return x;
	return father[x] = find2(father[x]);
}
int find3(int x){
	if(father3[x]==x)return x;
	return father3[x] = find1(father3[x]);
}
vector<int>cykle[1010];

int construct(std::vector<std::vector<int>> p) {
	int n = p.size(), i, j;
	for(i=0;i<n;i++)father[i] = father1[i] = i;
	std::vector<std::vector<int>> answer = p;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			answer[i][j] = 0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++){
			if(p[i][j]==3 || (i==j && p[i][j]!=1) || (p[i][j]!=p[j][i]))
				return 0;
			if(p[i][j]>0)
				father1[find1(i)] = find1(j);
			else
				if(find1(i)==find2(j))return 0;
			if(p[i][j]==1 && find2(i)!=find2(j)){
				father[find2(i)] = find2(j);
				answer[i][j] = answer[j][i] = 1;
			}
		}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(p[i][j]==2 && find2(i)==find2(j))
				return 0;
	for(i=0;i<n;i++)
		father3[i] = find2(i);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(p[i][j]==2 && find3(find2(i))!=find3(find2(j))){
				cykle[min(find2(i), find2(j))].push_back(max(find2(i), find2(j)));
				father3[max(find2(i), find2(j))] = min(find2(i), find2(j));
			}
	for(int j=0;j<n;j++){
		if(cykle[j].size()==2)return 0;
		for(i=0;i<(int)cykle[j].size();i++){
			int mod = cykle[j].size();
			answer[cykle[j][i]][cykle[j][(i+1)%mod]] = 1;
			answer[cykle[j][(i+1)%mod]][cykle[j][i]] = 1;
		}
	}
	build(answer);
	return 1;
}

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