제출 #675542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675542		speedyArda	슈퍼트리 잇기 (IOI20_supertrees)	C++14	46 / 100	212 ms	22176 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;
		twos[i] = 0;
	}
	bool valid = true;
	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(findset(i) == findset(a) && p[i][a] == 0)
					valid = false;
				if(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 < elems[i].size(); l++)
			{
				if(p[a][elems[i][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;
			torem.push_back(v);
			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 l = 0; l < torem.size(); l++)
			{
				for(int a = 0; a < torem.size(); a++)
				{
					if(l == a)
						continue;
					if(p[torem[l]][torem[a]] != 1)
						valid = false;
				}
			}
			for(int e : torem) 
				curr.erase(e);
			
		}

		if(incycle.size() > 1)
			answer[incycle.back()][incycle[0]] = answer[incycle[0]][incycle.back()] = 1;
		for(int l = 0; l < elems[i].size(); l++)
		{
			for(int a = 0; a < elems[i].size(); a++)
			{
				//if(elems[i][l] == elems[i][a])
					//continue;
				if(p[elems[i][l]][elems[i][a]] == 0)
					valid = false;
			}
		}
		for(int l = 0; l < incycle.size(); l++)
		{
			for(int a = 0; a < incycle.size(); a++)
			{
				if(incycle[l] == incycle[a])
					continue;
				if(p[incycle[l]][incycle[a]] != 2)
					valid = false;
			}
		}
		//else if(incycle.size() == 1)
			//valid = false;


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

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(int l = 0; l < elems[i].size(); l++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    for(int l = 0; l < torem.size(); l++)
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int a = 0; a < torem.size(); a++)
      |                    ~~^~~~~~~~~~~~~~
supertrees.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for(int l = 0; l < elems[i].size(); l++)
      |                  ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:131:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    for(int a = 0; a < elems[i].size(); a++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int l = 0; l < incycle.size(); l++)
      |                  ~~^~~~~~~~~~~~~~~~
supertrees.cpp:141:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |    for(int a = 0; a < incycle.size(); a++)
      |                   ~~^~~~~~~~~~~~~~~~

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