Submission #1198103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198103		HappyCapybara	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	140 ms	22200 KiB

supertrees

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

vector<int> p;

int find(int a){
	if (a == p[a]) return p[a];
	return p[a] = find(p[a]);
}

void merge(int a, int b){
	a = find(a);
	b = find(b);
	if (a != b) p[b] = a;
}

int construct(vector<vector<int>> a){
	int n = a.size();
	p.resize(n);
	for (int i=0; i<n; i++) p[i] = i;
	for (int i=0; i<n; i++){
		for (int j=i+1; j<n; j++){
			if (a[i][j] == 3) return 0;
			if (a[i][j] > 0) merge(i, j);
		}
	}
	for (int i=0; i<n; i++){
		for (int j=i+1; j<n; j++){
			if (a[i][j] == 0 && find(i) == find(j)) return 0;
		}
	}
	vector<vector<int>> cc(n);
	for (int i=0; i<n; i++) cc[find(i)].push_back(i);
	for (int i=0; i<n; i++) p[i] = i;
	for (int i=0; i<n; i++){
		for (int j=i+1; j<n; j++){
			if (a[i][j] == 1) merge(i, j);
		}
	}
	for (int i=0; i<n; i++){
		for (int j=i+1; j<n; j++){
			if (a[i][j] == 2 && find(i) == find(j)) return 0;
		}
	}
	vector<vector<int>> ans(n, vector<int>(n, 0));
	for (int i=0; i<n; i++){
		if (i != find(i)) ans[i][find(i)] = ans[find(i)][i] = 1;
		vector<int> cy;
		for (int x : cc[i]){
			if (x == find(x)) cy.push_back(x);
		}
		if (cy.size() == 1) continue;
		if (cy.size() == 2) return 0;
		for (int i=0; i<cy.size(); i++) ans[cy[i]][cy[(i+1)%cy.size()]] = ans[cy[(i+1)%cy.size()]][cy[i]] = 1;
	}
	build(ans);
	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