Submission #404598

#	Time	Username	Problem	Language	Result	Execution time	Memory
404598		monus1042	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	245 ms	28032 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;
		}
	}
	// 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 == x) 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;
}

Compilation message (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:66:11: warning: self-comparison always evaluates to true [-Wtautological-compare]
   66 |     if (x == x) return 0;
      |         ~ ^~ ~

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