답안 #432091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432091	2021-06-17T20:29:09 Z	peuch	슈퍼트리 잇기 (IOI20_supertrees)	C++17	0 / 100	1 ms	204 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;

int rep[MAXN];
vector<int> grp[MAXN];

int find(int a);
void uni(int a, int b);

int construct(vector<vector<int> > p) {
	int n = p.size();
	vector<vector<int> > ans (n, vector<int> (n));
	
	for(int i = 0; i < n; i++){
		rep[i] = i;
		grp[i].push_back(i);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 0) continue;
			uni(i, j);
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] != 0) continue;
			if(find(i) == find(j)) return 0;
		}
	}
	
	for(int i = 0; i < n; i++){
		if(i != rep[i]) continue;
		for(int j = 0; j < grp[i].size(); i++){
			for(int k = 0; k < grp[i].size(); k++){
				int a = grp[i][j], b = grp[i][k];
				if(p[a][b] != 1) return 0;
			}
		}
		for(int j = 1; j < grp[i].size(); i++){
			int a = grp[i][j], b = grp[i][j - 1];
			ans[a][b] = 1;
			ans[b][a] = 1;
		}
	}
	
	build(ans);
	return 1;
}

int find(int a){
	if(a == rep[a]) return a;
	return rep[a] = find(rep[a]);
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	if(grp[a].size() < grp[b].size()) swap(a, b);
	for(int i = 0; i < grp[b].size(); i++)
		grp[a].push_back(grp[b][i]);
	grp[b].clear();
	rep[b] = a;
	return;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int j = 0; j < grp[i].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
supertrees.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for(int k = 0; k < grp[i].size(); k++){
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j = 1; j < grp[i].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
supertrees.cpp: In function 'void uni(int, int)':
supertrees.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < grp[b].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 KB	Too few ways to get from 0 to 1, should be 1 found 0
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 KB	Too few ways to get from 0 to 1, should be 1 found 0
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Incorrect	1 ms	204 KB	Answer gives possible 0 while actual possible 1
6	Halted	0 ms	0 KB	-