제출 #1079269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079269		Jawad_Akbar_JJ	슈퍼트리 잇기 (IOI20_supertrees)	C++17	40 / 100	155 ms	22248 KiB

supertrees

#include <iostream>
#include <vector>
#include <algorithm>

#include "supertrees.h"

using namespace std;
const int NN = 1005;
int seen[NN];

int construct(vector<vector<int>> p){
	int n = p.size();
	vector<vector<int>> ans(n, vector<int> (n, 0)), comp, comp2;
	vector<int> out;

	int z = 0, o = 0, t = 0, th = 0; 
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++){
			z += p[i][j] == 0;
			o += p[i][j] == 1;
			t += p[i][j] == 2;
			th += p[i][j] == 3;
		}

	if (o and z + t + th == 0){
		for (int i=1;i<n;i++)
			ans[i-1][i] = ans[i][i-1] = 1;
		build(ans);
		return 1;
	}

	if (t + th == 0){

		for (int i=0;i<n;i++){
			int mx = 0, ind = -1;
			for (int k=0;k<comp.size();k++){
				int cnt = 0;
				for (int j : comp[k])
					cnt += p[i][j];
				if (cnt == 0)
					continue;
				if (mx > 0 or cnt != comp[k].size())
					return 0;
				ind = k;
				mx = cnt;
			}
			if (ind == -1)
				comp.push_back({i});
			else
				comp[ind].push_back(i);
		}

		for (auto v : comp)
			for (int j=1;j<v.size();j++)
				ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1;
		build(ans);
		return 1;
	}

	if (o == n and th == 0){
		for (int i=0;i<n;i++){
			int mx = 0, ind = -1;
			for (int k=0;k<comp.size();k++){
				int cnt = 0;
				for (int j : comp[k])
					cnt += p[i][j] == 2;
				if (cnt == 0)
					continue;
				if (mx > 0 or cnt != comp[k].size())
					return 0;
				ind = k;
				mx = cnt;
			}
			if (ind == -1)
				comp.push_back({i});
			else
				comp[ind].push_back(i);
		}

		for (auto v : comp){
			for (int j=1;j<v.size();j++)
				ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1;
			if (v.size() > 1)
				ans[v.back()][v[0]] = ans[v[0]][v.back()] = 1;
			if (v.size() == 2)
				return 0;
		}
		build(ans);
		return 1;
	}
	vector<pair<int,int>> vec;
	if (th == 0){
		for (int i=0;i<n;i++){
			int mx = 0, ind = -1;
			for (int k=0;k<comp.size();k++){
				int cnt = 0;
				for (int j : comp[k])
					cnt += p[i][j] == 2;
				if (cnt == 0)
					continue;
				if (cnt == comp[k].size()){
					ind = k;
					mx = cnt;
				}
			}
			if (ind == -1)
				comp.push_back({i});
			else
				comp[ind].push_back(i);
		}
		for (int i=0;i<comp.size();i++)
			vec.push_back({comp[i].size(), i});
		sort(begin(vec), end(vec));

		for (auto [sz, idx] : vec){
			vector<int> v = comp[idx];
			if (v.size() > 2){
				bool poss = 1;
				for (int i : v){
					if (seen[i])
						poss = 0;
					seen[i] = 1;
				}
				if (!poss)
					continue;
				for (int j=1;j<v.size();j++)
					ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1;
				ans[v.back()][v[0]] = ans[v[0]][v.back()] = 1;
				for (int i : v){
					for (int j=0;j<n;j++)
						if (i != j and p[i][j] == 1 and !seen[j])
							ans[i][j] = ans[j][i] = seen[j] = 1;
				}
			}
		}
		comp.clear();

		for (int i=0;i<n;i++){
			if (seen[i])
				continue;
			int mx = 0, ind = -1;
			for (int k=0;k<comp.size();k++){
				int cnt = 0;
				for (int j : comp[k])
					cnt += p[i][j] == 1;
				if (cnt == 0)
					continue;
				if (cnt == comp[k].size()){
					ind = k;
					mx = cnt;
				}
			}
			if (ind == -1)
				comp.push_back({i});
			else
				comp[ind].push_back(i);
		}

		for (auto v : comp){
			for (int j=1;j<v.size();j++)
				ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1;
		}

		build(ans);
		return 1;
	}

}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for (int k=0;k<comp.size();k++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     if (mx > 0 or cnt != comp[k].size())
      |                   ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int j=1;j<v.size();j++)
      |                 ~^~~~~~~~~
supertrees.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for (int k=0;k<comp.size();k++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if (mx > 0 or cnt != comp[k].size())
      |                   ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for (int j=1;j<v.size();j++)
      |                 ~^~~~~~~~~
supertrees.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for (int k=0;k<comp.size();k++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     if (cnt == comp[k].size()){
      |         ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:94:8: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   94 |    int mx = 0, ind = -1;
      |        ^~
supertrees.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (int i=0;i<comp.size();i++)
      |                ~^~~~~~~~~~~~
supertrees.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int j=1;j<v.size();j++)
      |                  ~^~~~~~~~~
supertrees.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |    for (int k=0;k<comp.size();k++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:148:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     if (cnt == comp[k].size()){
      |         ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:141:8: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
  141 |    int mx = 0, ind = -1;
      |        ^~
supertrees.cpp:160:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |    for (int j=1;j<v.size();j++)
      |                 ~^~~~~~~~~
supertrees.cpp:13:47: warning: control reaches end of non-void function [-Wreturn-type]
   13 |  vector<vector<int>> ans(n, vector<int> (n, 0)), comp, comp2;
      |                                               ^

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