Submission #339242

#	Time	Username	Problem	Language	Result	Execution time	Memory
339242		Ta180m	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	276 ms	22420 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MX = 1005;


int st[MX], cy[MX];
vector<int> vst[MX], vcy[MX];


int construct(vector<vector<int>> p) {
	int N = p.size();
	vector<vector<int>> ans(N, vector<int>(N));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (p[i][j] == 3) return 0;
		}
	}
	
	int cnt_st = 0;
	for (int i = 0; i < N; ++i) {
		if (!st[i]) {
			st[i] = ++cnt_st;
			vst[st[i]].push_back(i);
		}
		for (int j = 0; j < N; ++j) {
			if (p[i][j] != 1 || i == j || st[j] == st[i]) continue;
			if (st[j] && st[j] != st[i]) return 0;
			st[j] = st[i];
			vst[st[j]].push_back(j);
		}
	}

	for (int i = 1; i <= cnt_st; ++i) {
		for (int j = 1; j < vst[i].size(); ++j) {
			ans[vst[i][j-1]][vst[i][j]] = 1;
			ans[vst[i][j]][vst[i][j-1]] = 1;
		}
	}

	int cnt_cy = 0;
	for (int i = 1; i <= cnt_st; ++i) {
		int a = vst[i][0];
		if (!cy[a]) {
			cy[a] = ++cnt_cy;
			vcy[cy[a]].push_back(a);
		}
		for (int j = 1; j <= cnt_st; ++j) {
			int b = vst[j][0];
			if (p[a][b] != 2 || a == b || cy[a] == cy[b]) continue;
			if (cy[b] && cy[b] != cy[a]) return 0;
			cy[b] = cy[a];
			vcy[cy[b]].push_back(b);
		}
	}

	for (int i = 1; i <= cnt_cy; ++i) {
		int sz = vcy[i].size();
		if (sz == 1) continue;
		for (int j = 0; j < sz; ++j) {
			ans[vcy[i][j]][vcy[i][(j+1)%sz]] = 1;
			ans[vcy[i][(j+1)%sz]][vcy[i][j]] = 1;
		}
	}


	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (p[i][j] == 0) {
				if (st[i] == st[j] || cy[vst[st[i]][0]] == cy[vst[st[j]][0]]) return 0;
			}
			else if (p[i][j] == 1) {
				if (st[i] != st[j] || cy[vst[st[i]][0]] != cy[vst[st[j]][0]]) return 0;
			}
			else {
				if (st[i] == st[j] || cy[vst[st[i]][0]] != cy[vst[st[j]][0]]) return 0;
			}
		}
	}

	build(ans);
	return 1;
}

Compilation message (stderr)

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

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