Submission #532782

#	Time	Username	Problem	Language	Result	Execution time	Memory
532782		aryan12	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	279 ms	26736 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);
vector<vector<int> > answer;
vector<int> bruh(N, -1);
vector<int> representative(N, -1);

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);
	}
}

void lmao(int node, int okbruh) {
	bruh[node] = okbruh;
	if(node != okbruh) {
		answer[node][okbruh] = 1;
		answer[okbruh][node] = 1;
	}
	vis[node] = true;
	for(int i = 0; i < g[node].size(); i++) {
		if(vis[g[node][i]]) continue;
		lmao(g[node][i], okbruh);
	}
}

int construct(vector<vector<int> > input) {
	int n = input.size();
	answer.resize(n, vector<int> (n, 0));
	for(int i = 0; i < n; i++) {
		parent_component[i] = i;
		representative[i] = i;
		vis[i] = false;
		for(int j = 0; j < n; j++) {
			answer[i][j] = 0;
		}
	}
	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;
		if(components[i].size() == 2) {
			return 0;
		}
		//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) {
					//cout << "components[i][j] = " << components[i][j] << ", components[i][k] = " << components[i][k] << "\n";
					if(representative[components[i][j]] == components[i][j]) {
						representative[components[i][k]] = components[i][j];
					}
				}
			}
		}
		int prev = -1, first_one = -1;
		for(int j = 0; j < components[i].size(); j++) {
			//cout << "components[i][j] = " << components[i][j] << ", representative = " << representative[components[i][j]] << "\n";
			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];
			}
			else {
				answer[components[i][j]][representative[components[i][j]]] = 1;
				answer[representative[components[i][j]]][components[i][j]] = 1;
			}
		}
		//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) {
					//cout << "same representative node1 = " << node1 << ", node2 = " << node2 << "\n";
					return 0;
				}
				if(representative[node1] != representative[node2] && input[node1][node2] != 2) {
					//cout << "diff representative node1 = " << node1 << ", node2 = " << node2 << "\n";
					//cout << representative[node1] << ", " << representative[node2] << "\n";
					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";
		}
	}
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			lmao(i, i);
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(bruh[i] == bruh[j] && input[i][j] == 0) {
				return 0;
			}
		}
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int, int)':
supertrees.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
supertrees.cpp: In function 'void lmao(int, int)':
supertrees.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int j = 0; j < components[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for(int k = j + 1; k < components[i].size(); k++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int j = 0; j < components[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for(int j = 0; j < components[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    for(int k = 0; k < components[i].size(); k++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~

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