Submission #1225123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225123		Nonoze	슈퍼트리 잇기 (IOI20_supertrees)	C++20	40 / 100	121 ms	22224 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define fi first
#define se secod
#define sz(x) (int)x.size()
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back

using namespace std;

int n;
vector<int> par, sz;

int getpar(int x) {
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}

bool same(int a, int b) {
	return getpar(a)==getpar(b);
}

bool unite(int a, int b) {
	a=getpar(a), b=getpar(b);
	if (a==b) return 1;
	if (sz[a]<sz[b]) swap(a, b);
	sz[a]+=sz[b], par[b]=a;
	return 1;
}

int construct(vector<vector<int>> p) {
	n = sz(p);
	par.resize(n), sz.resize(n, 1); iota(all(par), 0);
	vector<vector<int>> answer(n, vector<int>(n, 0));
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			if (p[i][j] && !unite(i, j)) return 0;
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (!p[i][j] && same(i, j)) return 0;
		}
	}
	vector<vector<int>> vec(n);
	for (int i=0; i<n; i++) {
		vec[getpar(i)].pb(i);
	}
	for (int i=0; i<n; i++) if (sz(vec[i])>1) {
		for (int j=1; j<sz(vec[i]); j++) {
			answer[vec[i][j-1]][vec[i][j]]=answer[vec[i][j]][vec[i][j-1]]=1;
		}
		if (p[vec[i][0]][vec[i][1]]==2) {
			if (sz(vec[i])==2) return 0;
			answer[vec[i][0]][vec[i].back()]=answer[vec[i].back()][vec[i][0]]=1;
		}
	}
	build(answer);
	return 1;
}

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