제출 #675507

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

supertrees

#include "supertrees.h"
//#include <vector>
#define vi vector<int>
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1005;
int par[MAXN];
int twos[MAXN];
vector<vector<int> > elems(MAXN);

auto cmp = [](int a, int b)
{
	//cout << a << " " << b << "\n";
	if(twos[a] != twos[b])
		return twos[a] > twos[b];
	else
		return a > b;
};
int findset(int a)
{
	if(par[a] == a)
		return a;
	return par[a] = findset(par[a]);
}
int mergeset(int a, int b)
{
	a = findset(a), b = findset(b);
	if(a == b)
		return 0;
	//if(a > b)
		//swap(a,b);
	par[b] = a;
	return a;	
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n, vector<int>(n));
	for(int i = 0; i < n; i++)
		par[i] = i;
	for(int i = 0; i < n; i++)
	{
		if(findset(i) == i) // New component
		{
			elems[i].push_back(i);
			for(int a = 0; a < n; a++)
			{
				if(i == a || p[i][a] == 0)
					continue;
				//cout << i << " " << a << "\n";
				if(findset(a) == a)
				{
					mergeset(i, a);
					elems[i].push_back(a);
				}
			}
		}
	}

	bool valid = true;
	for(int i = 0; i < n; i++)
	{
		vi incycle;
		if(elems[i].size() == 0)
			continue;
		set<int, decltype(cmp)> curr(cmp);
		
		for(int a : elems[i])
		{
			for(int l = 0; l < n; l++)
			{
				if(p[a][l] == 2)
					twos[a]++;
			}
			//cout << a << ""
			curr.insert(a);
		}
		int lastelem = -1;
		//for(int e : curr)
			//cout << "Hm: " << e << "\n"; 
		while(!curr.empty())
		{
			int v = *(curr.begin());
			//cout << v << "\n";
			curr.erase(curr.begin());
			if(incycle.size() > 0)
			{
				lastelem = incycle.back();
				//cout << v << " " << lastelem
				answer[v][lastelem] = answer[lastelem][v] = 1;
				
			}
			incycle.push_back(v);
			//cout << v << " " << curr.size() << "\n";
			vi torem;
			for(int a : curr)
			{	
				//cout << v << " " << a << " " << p[a][v] << "\n";
				if(p[v][a] == 1) {
					//cout << v << " " << a << "\n";
					answer[v][a] = answer[a][v] = 1;
					torem.push_back(a);
					//curr.erase(a);
				}
			}
			for(int e : torem)
				curr.erase(e);
			
		}

		if(incycle.size() > 1)
			answer[incycle.back()][incycle[0]] = answer[incycle[0]][incycle.back()] = 1;
		else if(incycle.size() == 1)
			valid = false;


	}
	//if(incycle[i] != )
	if(valid) {
		build(answer);
		return 1;
	}
	else
		return 0;
}

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