제출 #417500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417500		Chaska	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	279 ms	27972 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n ;
int a[N][N];
int dad[N];
bool vs[N];
bool act[N];
struct UnionFind {
	int ran;
	int da;
};
UnionFind uf[N];
vector<std::vector<int>> answer;
vector<int> g[N];
int bus(int u)
{
	if (uf[u].da != u) uf[u].da = bus(uf[u].da);
	return uf[u].da;
}
void unir(int u,int v)
{
	u = bus(u);
	v = bus(v);
	if (u != v) {
		if (uf[u].ran > uf[v].ran) uf[v].da = u;
		else if (uf[u].ran < uf[v].ran) uf[u].da = v;
		else {
			uf[u].ran++;
			uf[v].da = u;
		}
	}
	return;
}
int construct(std::vector<std::vector<int>> _p) {
	n = _p.size();
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = _p[i][j];
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] > 2) 
		return 0;
	for (int i=0;i<n;i++) {
		uf[i].ran = 0;
		uf[i].da = i;
	}
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]>0) unir(i,j);
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] == 0) if (bus(i) == bus(j)) {
		return 0;
	}
	for (int i=0;i<n;i++) g[bus(i)].push_back(i);
	for (int x=0;x<n;x++) {

			uf[x].da = x;
			uf[x].ran = 0;
 	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<(int)g[i].size();j++) act[g[i][j]] = true;

		for (int j=0;j<(int)g[i].size();j++) {
			int x = g[i][j];
			for (int k=0;k<(int)g[i].size() && act[x];k++) {
				int y = g[i][k];
				if (x != y) {
					if (a[x][y] == 1) {
						unir(x,y);
					}
				}
			}
		} 
		vector<int> gg;
		set<int> s;
		for (int j=0;j<(int)g[i].size();j++) s.insert(bus(g[i][j]));
		for (int u : s) gg.push_back(u);
		for (int j=1;j<(int)gg.size();j++) {
			answer[gg[j]][gg[j-1]] = answer[gg[j-1]][gg[j]] = 1;
		}
		int  pp = gg.size();
		if (pp>1) answer[gg[0]][gg[pp-1]] = answer[gg[pp-1]][gg[0]] = 1;
		for (int j=0;j<(int)g[i].size();j++) if (g[i][j] != bus(g[i][j])) {
			int x = g[i][j];
			answer[x][bus(x)] = answer[bus(x)][x] = 1;
		}
	}
	build(answer);
	return 1;
}

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