Submission #416129

#	Time	Username	Problem	Language	Result	Execution time	Memory
416129		pavement	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	348 KiB

supertrees

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

#define pb push_back
#define eb emplace_back

int n, link[1005], sz[1005], link2[1005], sz2[1005];
vector<int> vec[1005], vec2[1005];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	cout << "UN " << a << ' ' << b << '\n';
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	for (int i : vec[b]) vec[a].pb(i);
	link[b] = a;
}

int find2(int x) {
	if (x == link2[x]) return x;
	return link2[x] = find2(link2[x]);
}

void unite2(int a, int b) {
	a = find2(a);
	b = find2(b);
	if (a == b) return;
	if (sz2[b] > sz2[a]) swap(a, b);
	sz2[a] += sz2[b];
	for (int i : vec2[b]) vec2[a].pb(i);
	link2[b] = a;
}

vector<pair<int, int> > tmp;

int construct(vector<vector<int> > p) {
	::n = p.size();
	vector<vector<int> > b(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		link[i] = link2[i] = i;
		sz[i] = sz2[i] = 1;
		vec[i].pb(i);
		vec2[i].pb(i);
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 1) unite(i, j);
			else if (p[i][j] == 2) tmp.eb(i, j);
		}
	for (int i = 0; i < n; i++)
		if (i == find(i))
			for (int j = 0; j < (int)vec[i].size() - 1; j++) {
				cout << "LINK " << vec[i][j] << ' ' << vec[i][j + 1] << '\n';
				b[vec[i][j]][vec[i][j + 1]] = 1;
			}
	for (auto i : tmp)
		unite2(find(i.first), find(i.second));
	for (int i = 0; i < n; i++)
		if (i == find2(i))
			for (int j = 0; j < vec2[i].size(); j++) {
				cout << "YEP " << vec2[i][j] << ' ' << vec2[i][(j + 1) % vec2[i].size()] << '\n';
				b[vec2[i][j]][vec2[i][(j + 1) % vec2[i].size()]] = 1;
			}
	build(b);
	return 1;
}

Compilation message (stderr)

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

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