Submission #1018335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018335		Boas	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	128 ms	28176 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef set<int> si;
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<ii> vii;
#define loop(x, i) for (int i = 0; i < (x); i++)
#define ALL(x) (x).begin(), x.end()
#define pb push_back

vvi adj, ans;
int N;
vi components;
vb hasCycle;
vector<vvi> cycleTakken;

bool dfs(int i, int c)
{
	components[i] = c;
	loop(N, j)
	{
		if (adj[i][j] > 0)
		{
			if (components[j] == c)
				continue;
			if (components[j] != -1)
				return 0;
			// ans[i][j] = 1;
			// ans[j][i] = 1;
			if (!dfs(j, c))
				return 0;
		}
	}
	return 1;
}

vb inTak;

bool cycleFinder(int i, int c)
{
	inTak[i] = 1;
	loop(N, j)
	{
		if (inTak[j])
			continue;
		if (adj[i][j] == 1)
		{
			for (int k : cycleTakken[c].back())
			{
				if (adj[j][k] != 1)
				{
					return 0;
				}
			}
			cycleTakken[c].back().pb(j);
			cycleFinder(j, c);
		}
	}
	return 1;
}

int construct(vvi p)
{
	N = p.size();
	adj = p;
	components = vi(N, -1);
	int c = 0;
	ans = vvi(N, vi(N));
	loop(N, i)
	{
		if (components[i] == -1)
		{
			if (!dfs(i, c))
				return 0;
			c++;
		}
	}
	loop(N, i)
	{
		loop(N, j)
		{
			if (i == j)
				continue;
			if (p[i][j] == 0 && components[i] == components[j])
				return 0;
			if (p[i][j] > 0 && components[i] != components[j])
				return 0;
			if (p[i][j] == 3)
				return 0;
		}
	}
	hasCycle.resize(c);
	loop(N, i)
	{
		if (hasCycle[components[i]])
			continue;
		loop(N, j)
		{
			if (p[i][j] == 2)
			{
				hasCycle[components[i]] = 1;
				break;
			}
		}
	}
	inTak = vb(N);
	cycleTakken.resize(c);
	loop(N, i)
	{
		int k = components[i];
		if (inTak[i])
			continue;
		cycleTakken[k].pb({i});
		if (!cycleFinder(i, k))
			return 0;
	}
	loop(c, k)
	{
		// if (!hasCycle[k]) continue;
		vi uiteinden;
		if (cycleTakken[k].size() == 2)
			return 0;
		for (vi tak : cycleTakken[k])
		{
			uiteinden.pb(tak.back());
			for (int i = 1; i < tak.size(); i++)
			{
				ans[tak[i]][tak[i - 1]] = 1;
				ans[tak[i - 1]][tak[i]] = 1;
			}
		}
		if (uiteinden.size() >= 2)
		{
			ans[uiteinden[0]][uiteinden.back()] = 1;
			ans[uiteinden.back()][uiteinden[0]] = 1;
			for (int i = 1; i < uiteinden.size(); i++)
			{
				ans[uiteinden[i]][uiteinden[i - 1]] = 1;
				ans[uiteinden[i - 1]][uiteinden[i]] = 1;
			}
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

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

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