Submission #1178934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178934		cot7302	슈퍼트리 잇기 (IOI20_supertrees)	C++20	19 / 100	118 ms	22280 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)

namespace {

using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

struct Unionfind {
	vec<int> p;
	Unionfind(int N) : p(N, -1) {};

	int find(int x) {
		return p[x] < 0 ? x : (p[x] = find(p[x]));
	}

	void join(int x, int y) {
		if ((x = find(x)) == (y = find(y))) {
			return;
		}
		if (p[x] > p[y]) {
			swap(x, y);
		}
		p[x] += exchange(p[y], x);
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

}

int construct(std::vector<std::vector<int>> p) {
	int N = size(p);
	Unionfind uf(N);
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (p[i][j] == 3) {
				return 0;
			}
			if (p[i][j] == 1) {
				uf.join(i, j);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (p[i][j] != 1 && uf.same(i, j)) {
				return 0;
			}
		}
	}
	vec<int> rep(N);
	vec<vec<int>> ccs(N);
	for (int i = 0; i < N; i++) {
		rep[i] = uf.find(i);
		ccs[uf.find(i)].emplace_back(i);
	}
	fill(ALL(uf.p), -1);
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (p[i][j] == 3) {
				return 0;
			}
			if (p[i][j] == 2) {
				uf.join(i, j);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (p[i][j] == 0 && uf.same(i, j)) {
				return 0;
			}
		}
	}
	vec<int> rep2(N);
	vec<vec<int>> ccs2(N);
	for (int i = 0; i < N; i++) {
		rep2[i] = uf.find(i);
		ccs2[uf.find(i)].emplace_back(i);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 1; j < (int)size(ccs[i]); j++) {
			if (rep2[ccs[i][j - 1]] != rep2[ccs[i][j]]) {
				return 0;
			}
		}
	}
	vec<vec<int>> ans(N, vec<int>(N));
	for (int i = 0; i < N; i++) {
		if (size(ccs[i]) == 1) {
			continue;
		}
		for (int j = 1; j < (int)size(ccs[i]); j++) {
			int u = ccs[i][j - 1];
			int v = ccs[i][j];
			ans[u][v] = ans[v][u] = 1;
		}
	}
	for (int i = 0; i < N; i++) {
		if (size(ccs2[i]) == 1) {
			continue;
		}
		for (auto& x : ccs2[i]) {
			x = rep[x];
		}
		sort(ALL(ccs2[i]));
		ccs2[i].resize(unique(ALL(ccs2[i])) - begin(ccs2[i]));
		if (size(ccs2[i]) == 2) {
			return 0;
		}
		assert(size(ccs2[i]) != 1);
		int n = size(ccs2[i]);
		for (int j = 0; j < n; j++) {
			int u = ccs2[i][j];
			int v = ccs2[i][(j + 1) % n];
			ans[u][v] = ans[v][u] = 1;
		}
	}
	build(ans);
	return 1;
}

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