Submission #1288251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288251		harryleee	슈퍼트리 잇기 (IOI20_supertrees)	C++20	11 / 100	88 ms	22028 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);
		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[v]) 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[0].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 (p[i][j] != 0) dsu.merge(i, j);
	// 	}
	// }

	// for (int i = 0; i < n; ++i){
	// 	for (int j = 0; j < n; ++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;
	// }
	vector<vector<int>> a (n, vector<int> (n, 0));
	for (int i = 0; i < n - 1; ++i)
		a[i][i + 1] = a[i + 1][i] = 1;
	build(a);
	return 1;
}

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