Submission #532756

#	Time	Username	Problem	Language	Result	Execution time	Memory
532756		aryan12	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	332 KiB

supertrees

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

const int N = 1010;
int parent_component[N];
vector<int> components[N];
vector<int> g[N];
vector<bool> vis(N);

int Find(int x) {
	if(x == parent_component[x]) return x;
	return parent_component[x] = Find(parent_component[x]);
}

void Unite(int a, int b) {
	a = Find(a), b = Find(b);
	if(a > b) swap(a, b);
	parent_component[b] = a;
}

void dfs(int node, int total_par) {
	parent_component[node] = total_par;
	components[total_par].push_back(node);
	vis[node] = true;
	for(int i = 0; i < g[node].size(); i++) {
		if(vis[g[node][i]]) continue;
		dfs(g[node][i], total_par);
	}
}

bool isCycle(int node, int par) {
	vis[node] = true;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] == par) continue;
		if(vis[g[node][i]]) return false;
		bool x = isCycle(g[node][i], node);
		if(!x) return false;
	}
	return true;
}

int construct(vector<vector<int> > input) {
	int n = input.size();
	vector<int> representative(n, -1);
	vector<vector<int> > answer(n, vector<int> (n, 0));
	for(int i = 0; i < n; i++) {
		parent_component[i] = i;
		representative[i] = i;
		vis[i] = false;
	}
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(input[i][j] == 3) {
				return 0;
			}
			if(input[i][j] != 2) continue;
			g[i].push_back(j);
			g[j].push_back(i);
		}
	}
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			dfs(i, i);
		}
	}
	for(int i = 0; i < n; i++) {
		//cout << "parent_component[i] = " << parent_component[i] << "\n";
		parent_component[i] = Find(parent_component[i]);
	}
	for(int i = 0; i < n; i++) {
		if(i != parent_component[i] || components[i].size() == 1) continue;
		//cout << "i = " << i << "\n";
		sort(components[i].begin(), components[i].end());
		for(int j = 0; j < components[i].size(); j++) {
			//cout << "components[i][j] = " << components[i][j] << "\n";
			for(int k = j + 1; k < components[i].size(); k++) {
				if(input[components[i][j]][components[i][k]] == 1) {
					representative[components[i][k]] = components[i][j];
					//cout << "components[i][j] = " << components[i][j] << ", components[i][k] = " << components[i][k] << "\n";
					answer[components[i][j]][components[i][k]] = 1;
					answer[components[i][k]][components[i][j]] = 1;
				}
			}
		}
		int prev = -1, first_one = -1;
		for(int j = 0; j < components[i].size(); j++) {
			if(representative[components[i][j]] == components[i][j]) {
				if(prev == -1) {
					first_one = components[i][j];
				}
				else {
					answer[prev][components[i][j]] = 1;
					answer[components[i][j]][prev] = 1;
				}
				prev = components[i][j];
			}
		}
		//cout << "first_one = " << first_one << ", prev = " << prev << "\n";
		//cout << "first_one = " << first_one << ", prev = " << prev << "\n";
		answer[first_one][prev] = 1;
		answer[prev][first_one] = 1;
		for(int j = 0; j < components[i].size(); j++) {
			for(int k = 0; k < components[i].size(); k++) {
				int node1 = components[i][j], node2 = components[i][k];
				if(representative[node1] == representative[node2] && input[node1][node2] != 1) {
					return 0;
				}
				if(representative[node1] != representative[node2] && input[node1][node2] != 2) {
					return 0;
				}
			}
		}
		//cout << "hello\n";
	}
	for(int i = 0; i < n; i++) {
		g[i].clear();
		vis[i] = false;
	}
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(input[i][j] != 1) {
				continue;
			}
			if(Find(i) == Find(j)) continue;
			g[i].push_back(j);
			g[j].push_back(i);
			//cout << "i = " << i << ", j = " << j << "\n";
			if(i != Find(i) || j != Find(j)) {
				return 0;
			}
			answer[i][j] = 1;
			answer[j][i] = 1;
		}
	}
	for(int i = 0; i < n; i++) {
		if(!vis[i] && !isCycle(i, -1)) {
			return 0;
		}
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int, int)':
supertrees.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
supertrees.cpp: In function 'bool isCycle(int, int)':
supertrees.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int j = 0; j < components[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(int k = j + 1; k < components[i].size(); k++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int j = 0; j < components[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int j = 0; j < components[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for(int k = 0; k < components[i].size(); k++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~

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