Submission #640309

#	Time	Username	Problem	Language	Result	Execution time	Memory
640309		ymm	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	183 ms	24120 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 1010;

static vector<int> one[N];
static vector<int> two[N];
static bool vis[N];
static int col[N];
static vector<vector<int>> B;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	B = vector<vector<int>>(n, vector<int>(n, 0));
	Loop (i,0,n) Loop (j,0,n) {
		if (p[i][j] == 3)
			return 0;
	}
	int n1 = 0;
	Loop (i,0,n) {
		if (vis[i])
			continue;
		Loop (j,0,n)
			if (p[i][j] == 1) {
				one[n1].push_back(j);
				vis[j] = 1;
				col[j] = n1;
				if (i != j)
					B[i][j] = B[j][i] = 1;
			}
		for (int x : one[n1])
			for (int y : one[n1])
				if (p[x][y] != 1)
					return 0;
		++n1;
	}
	Loop (i,0,n1)
		Loop (j,i+1,n1)
			for (int x : one[i])
				for (int y : one[j])
					if (p[x][y] == 1)
						return 0;
	memset(vis, 0, sizeof(vis));
	int n2 = 0;
	Loop (i,0,n) {
		if (vis[col[i]])
			continue;
		vis[col[i]] = 1;
		two[n2].push_back(col[i]);
		Loop (j,0,n)
			if (p[i][j] == 2) {
				if (!vis[col[j]]) {
					two[n2].push_back(col[j]);
					vis[col[j]] = 1;
				}
			}
		if (two[n2].size() == 1) {
			n2++;
			continue;
		}
		for (int x : two[n2])
			for (int y : two[n2])
				if (x != y)
					for (int a : one[x])
						for (int b : one[y])
							if (p[a][b] != 2)
								return 0;
		if (two[n2].size() == 2) {
			if (one[two[n2][0]].size() >= 2) {
				B[one[two[n2][0]][0]][one[two[n2][1]][0]] = 1;
				B[one[two[n2][1]][0]][one[two[n2][0]][0]] = 1;
				B[one[two[n2][0]][1]][one[two[n2][1]][0]] = 1;
				B[one[two[n2][1]][0]][one[two[n2][0]][1]] = 1;
			} else if (one[two[n2][1]].size() >= 2) {
				B[one[two[n2][0]][0]][one[two[n2][1]][0]] = 1;
				B[one[two[n2][1]][0]][one[two[n2][0]][0]] = 1;
				B[one[two[n2][0]][0]][one[two[n2][1]][1]] = 1;
				B[one[two[n2][1]][1]][one[two[n2][0]][0]] = 1;
			} else {
				return 0;
			}
		}
		if (two[n2].size() >= 3) {
			Loop (i,0,two[n2].size()) {
				int j = (i+1) % two[n2].size();
				B[one[two[n2][i]][0]][one[two[n2][j]][0]] = 1;
				B[one[two[n2][j]][0]][one[two[n2][i]][0]] = 1;
			}
		}
		n2++;
	}
	Loop (i,0,n2)
		Loop (j,i+1,n2)
			for (int x : two[i])
				for (int y : two[j])
					for (int a : one[x])
						for (int b : one[y])
							if (p[a][b])
								return 0;
	build(B);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
supertrees.cpp:90:4: note: in expansion of macro 'Loop'
   90 |    Loop (i,0,two[n2].size()) {
      |    ^~~~

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