Submission #360950

#	Time	Username	Problem	Language	Result	Execution time	Memory
360950		Gurban	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	295 ms	24172 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

using ll = long long;

const int maxn=1e3+5;
int p[maxn];
int nw[maxn];
vector<int>v[maxn];

int ata(int nd){
	if(p[nd] == nd) return nd;
	return p[nd] = ata(p[nd]);
}

int par(int nd){
	if(nw[nd] == nd) return nd;
	return nw[nd] = ata(nw[nd]);
}

int construct(vector<vector<int>> a) {
	int n = a.size();
	for(int i = 0;i < n;i++) p[i] = nw[i] = i;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			if(a[i][j] == 3) return 0;
			if(a[i][j] == 1){
				int x = ata(i),y = ata(j);
				if(x != y) p[y] = x;
			}
		}
	}
	for(int i = 0;i < n;i++) ata(i);

	vector<vector<int>>ed;
	ed.resize(n);
	for(int i = 0;i < n;i++) ed[i].resize(n);
	
	for(int i = 0;i < n;i++){
		if(p[i] != i){
			if(a[i] != a[p[i]]) return 0;
			ed[p[i]][i] = 1;
			ed[i][p[i]] = 1;
		}
		else {
			for(int j = 0;j < n;j++){
				if(p[j] != j or i == j) continue;
				if(a[i][j] == 2){
					int x = par(i),y = par(j);
					if(x != y) nw[j] = i;
				}
			}
		}
	}
	
	for(int i = 0;i < n;i++){
		if(p[i] != i) continue;
		par(i);
		v[nw[i]].push_back(i);
	}
	for(int i = 0;i < n;i++){
		
		if(p[i] != i) continue;
		if(nw[i] != i) continue;
		
		if((int)v[i].size() == 2) return 0;

		for(int j = 0;j < (int)v[i].size();j++){
			for(int k = 0;k < j;k++){
				if(a[v[i][j]][v[i][k]] != 2) return 0;
			}
			if(j > 0){
				ed[v[i][j]][v[i][j-1]]=1;
				ed[v[i][j-1]][v[i][j]]=1;
			}
		}

		if((int)v[i].size() > 1) ed[v[i].back()][v[i][0]]=1;
		if((int)v[i].size() > 1) ed[v[i][0]][v[i].back()]=1;
	}

	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			if(i == j) continue;
			if(p[i] == p[j] and a[i][j] != 1) return 0;
			if(nw[i] == nw[j] and a[i][j] != 2) return 0;
			if(p[i] != p[j] and nw[p[i]] != nw[p[j]] and a[i][j] != 0) return 0;
		}
	}

	build(ed);
	return 1;
}

/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

2
1 0
0 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