제출 #404603

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

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
 
const int NAX = 1002;
vector<int> parent(NAX, -1), parent2(NAX, -1);
vector<vector<int> > answer;
 
vector<vector<int> > P(NAX, vector<int>(NAX));
vector<vector<int> > gsetone(NAX), adj(NAX);
 
int n;
 
int Find(int u){
	if (parent[u] == -1) return u;
	return parent[u] = Find(parent[u]);
}
 
int Find2(int u){
	if (parent2[u] == -1) return u;
	return parent2[u] = Find2(parent2[u]);
}
 
int construct(vector<vector<int> > p) {
	n = p.size();
	for (int i=0; i<n; i++){
		vector<int> row(n);
		answer.push_back(row);
	}
	
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			P[i][j] = p[i][j];
		}
	}
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (i==j) continue;
			if (P[i][j] == 1){ // first do the bamboos
				int x = Find(i), y = Find(j);
				if (x != y){
					parent[x] = y;
				}
			}
		}
	}
	for (int i=0; i<n; i++){
		int pp = Find(i);
		if (pp != i) gsetone[pp].push_back(i);
	}
	for (int i=0; i<n; i++){
		int u = i;
		for (int j=0; j<gsetone[i].size(); j++){
			int v = gsetone[i][j];
			answer[u][v] = answer[v][u] = 1;
			u = v;
		}
	}
	// do the twos
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (i==j) continue;
			if (P[i][j] == 2){
				int x = Find(i), y = Find(j);
				int X = Find2(x), Y = Find2(y);
				if (X != Y){
					parent2[X] = Y;
				}
			}
		}
	}
	for (int i=0; i<n; i++){
		int pp = Find(i);
		int PP = Find2(pp);
		if (PP != pp){
			adj[PP].push_back(i);
		}
	}
	for (int i=0; i<n; i++){
		if ((int)adj[i].size() == 1) return 0;
		int u = i;
		for (int j=0; j<adj[i].size(); j++){
			int v = adj[i][j];
			answer[u][v] = answer[v][u] = 1;
			u = v;
		}
		if ((int)adj[i].size() > 1) answer[u][i] = answer[i][u] = 1;
	}
	// check everything:
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (i==j) continue;
			int x = Find(i), y = Find(j);
			int X = Find2(x), Y = Find2(y);
			if (P[i][j] == 0){
				if (X == Y) return 0;
			}else if (P[i][j] == 1){
				if (x != y) return 0;
			}else{
				if (x == y || X != Y) return 0;
			}
		}
	}
	build(answer);
	return 1;
}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int j=0; j<gsetone[i].size(); j++){
      |                 ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int j=0; j<adj[i].size(); j++){
      |                 ~^~~~~~~~~~~~~~

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