Submission #339259

#	Time	Username	Problem	Language	Result	Execution time	Memory
339259		Ta180m	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	265 ms	24428 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], top[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]) continue;
		st[i] = ++cnt_st, vst[st[i]].push_back(i);
		for (int j = 0; j < N; ++j) {
			if (st[i] == st[j] || p[i][j] != 1) 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) {
		vector<int> & cur = vst[i];
		for (int j = 1; j < cur.size(); ++j)
			ans[cur[j-1]][cur[j]] = ans[cur[j]][cur[j-1]] = 1;
	}

	for (int i = 0; i < N; ++i) top[i] = vst[st[i]][0];

	int cnt_cy = 0;
	for (int i = 1; i <= cnt_st; ++i) {
		int a = vst[i][0];
		if (cy[a]) continue;
		cy[a] = ++cnt_cy, vcy[cy[a]].push_back(a);
		for (int j = 1; j <= cnt_st; ++j) {
			int b = vst[j][0];
			if (cy[a] == cy[b] || p[a][b] != 2) 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) {
		vector<int> & cur = vcy[i];
		int sz = cur.size();
		if (sz == 1) continue;
		if (sz == 2) return 0;
		for (int j = 0; j < sz; ++j)
			ans[cur[j]][cur[(j+1)%sz]] = ans[cur[(j+1)%sz]][cur[j]] = 1;
	}

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

	build(ans);
	return 1;
}

Compilation message (stderr)

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

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