제출 #1288234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288234		harryleee	슈퍼트리 잇기 (IOI20_supertrees)	C++20	0 / 100	1 ms	348 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int maxn = 1e3;

struct DSU{
	vector<int> par, sz, trace;
	int cnt;
	inline DSU(int n){
		par.resize(n, 0);
		sz.resize(n, 1);
		for (int i = 0; i < n; ++i) par[i] = i;
		trace.resize(n, -1);
		cnt = -1;
	}
	inline int find(int x){
		return (par[x] == x) ? x : (par[x] = find(par[x]));
	}
	inline void merge(int x, int y){
		int u = find(x), v = find(y);
		if (u == v) return;
		if (sz[u] < sz[x]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
		return;
	}
	inline int order(int x){
		int u = find(x);
		if (trace[u] == -1)
			trace[u] = ++cnt;
		return trace[u];
	}
};

int construct(vector<vector<int>> p){
	int n = p.size();
	vector<vector<int>> vec(n);
	vector<vector<int>> a (n, vector<int> (n, 0));
	DSU dsu(n);

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j) if (j != i){
			if (p[i][j] != 0) dsu.merge(i, j);
		}
	}

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j)if (i != j){
			if (p[i][j] == 0 && dsu.find(i) == dsu.find(j))
				return 0;
		}
	}

	for (int i = 0; i < n; ++i)
		vec[dsu.order(i)].push_back(i);
	int cnt = dsu.cnt;

	for (int k = 0; k < cnt; ++k){
		vector<int>& v = vec[k];
		for (int i = 0; i < v.size() - 1; ++i)
			a[v[i]][v[i + 1]] = a[v[i + 1]][v[i]] = 1;
	}
	build(a);
	return 1;
}

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