제출 #371335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371335		peijar	슈퍼트리 잇기 (IOI20_supertrees)	C++17	21 / 100	272 ms	24172 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

struct UnionFind
{
	vector<int> id;
	
	UnionFind() {}
	UnionFind(int N)
	{
		id.assign(N, -1);
	}

	int find(int u)
	{
		if (id[u] < 0) return u;
		return id[u] = find(id[u]);
	}

	bool merge(int u, int v)
	{
		u = find(u), v = find(v);
		if (u == v) return false;
		if (id[u] > id[v]) swap(u, v);
		id[u] += id[v];
		id[v] = u;
		return true;
	}

	vector<vector<int>> getComps()
	{
		vector<vector<int>> ret;
		vector<vector<int>> comps(SZ(id));
		for (int i(0); i < SZ(id); ++i)
			comps[find(i)].push_back(i);
		for (auto v : comps)
			if (SZ(v))
				ret.push_back(v);
		return ret;
	}
};

int construct(vector<vector<int>> p) {
	int nbSommets = SZ(p);
	vector<vector<int>> sol(nbSommets, vector<int>(nbSommets));

	UnionFind uf(nbSommets);
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (p[i][j])
				uf.merge(i, j);
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (uf.find(i) == uf.find(j) and p[i][j] == 0)
				return 0;
	for (int i(0); i < nbSommets; ++i)
		if (uf.find(i) != i)
			sol[uf.find(i)][i] = sol[i][uf.find(i)] = 1;

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