Submission #417543

#	Time	Username	Problem	Language	Result	Execution time	Memory
417543		ja_kingy	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	252 ms	23060 KiB

supertrees

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

const int mxN = 1000;
struct DSU {
	int dsu[mxN];
	DSU () {iota(dsu, end(dsu), 0);}
	int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
	void merge(int a, int b) {
		a = f(a), b = f(b);
		if (a!=b) dsu[a] = b;
	}
} ldsu, cdsu;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < n; ++j) {
		if (p[i][j] == 3) return 0;
		if (p[i][j]) {
			cdsu.merge(i,j);
		}
		if (p[i][j] == 1) {
			ldsu.merge(i,j);	
		}
	}

	for (int i = 0; i < n; i++) for (int j = 0; j < n; ++j) {
		if (p[i][j] == 0 && cdsu.f(i) == cdsu.f(j)) {
			return 0;
		}
		if (p[i][j] == 2 && ldsu.f(i) == ldsu.f(j)) {
			return 0;
		}
	}

	vector<vector<int>> ls(n), cs(n);
	for (int i = 0; i < n; ++i) {
		int l = ldsu.f(i);
		if (ls[l].size()) answer[ls[l].back()][i] = answer[i][ls[l].back()] = 1;
		ls[l].push_back(i);
	}

	for (int j = 0; j < n; ++j) if (ls[j].size()) {
		int i = ls[j].back();
		int c = cdsu.f(i);
		if (cs[c].size()) answer[cs[c].back()][i] = answer[i][cs[c].back()] = 1;
		cs[c].push_back(i);
	}

	for (int i = 0; i < n; ++i) if (cs[i].size()) {
		if (cs[i].size() == 2) return 0;
		if (cs[i].size() > 2) {
			answer[cs[i].back()][cs[i].front()] = answer[cs[i].front()][cs[i].back()] = 1;
		}
	}

	build(answer);
	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