제출 #1291373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291373		Ludissey	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	180 ms	26128 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

vector<int> parent;
vector<int> sz;

int getParent(int a){
	if(parent[a]==a) return a;
	return parent[a]=getParent(parent[a]);
}

void unite(int a, int b){
	a=getParent(a); b=getParent(b);
	if(a==b) return;
	if(sz[a]>sz[b]) swap(a,b);
	parent[b]=a;
	sz[a]+=sz[b];
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<signed>> answer(n,vector<int>(n));
	vector<pair<int,int>> ed;
	parent.resize(n);
	sz.resize(n,1);
	for (int i = 0; i < n; i++) parent[i]=i;
	vector<vector<int>> con(n,vector<int>(n,0));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
		{
			if(p[i][j]==1){
				if(getParent(i)==getParent(j)) continue;
				ed.push_back({i,j});
				unite(i,j);
			}
		}
	}

	for (int i = 0; i < n; i++) con[i][i]=1;
	

	vector<bool> used(n);
	for (int i = 0; i < n; i++)
	{
		if(used[getParent(i)]) continue;
		used[getParent(i)]=true;
		set<int> st;
		for (int j = 0; j < n; j++)
		{
			if(p[i][j]==2){
				st.insert(getParent(j));
			}
		}
		if(sz(st)==0) continue;
		if(sz(st)==1) return 0;
		int lst=getParent(i);
		for (auto u : st)
		{
			ed.push_back({u,lst});
			lst=u;
			used[u]=true;
		}
		ed.push_back({getParent(i),lst});
		st.insert(getParent(i));
		for (auto u : st){
			for (auto v : st){
				if(u==v) continue;
				con[u][v]=con[v][u]=2;
			}
		}

	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if(p[i][j]!=con[getParent(i)][getParent(j)]) return 0;
		}
	}
	
	for (auto u : ed)
	{
		answer[u.first][u.second]=answer[u.second][u.first]=1;
	}
	build(answer);
	return 1;
}

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