Submission #619679

#	Time	Username	Problem	Language	Result	Execution time	Memory
619679		AriaH	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	184 ms	22124 KiB

supertrees

#include "supertrees.h"
/* I can do this all day */

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);

const int N = 1e3 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[N];

vector < int > mol[N], vec[N];

vector < vector < int > > Ans;

inline void add(int i, int j)
{
	Ans[i][j] = Ans[j][i] = 1;
}

int get(int x)
{
	return (x == par[x]? x : par[x] = get(par[x]));
}

void unify(int v, int u)
{
	v = get(v), u = get(u);
	if(v == u) return;
	par[u] = v;
}

int construct(vector < vector < int > > A)
{
	int n = SZ(A);
	for(int i = 0; i < n; i ++) par[i] = i;
	Ans.resize(n);
	for(int i = 0; i < n; i ++)
	{
		Ans[i].resize(n, 0);
		if(A[i][i] != 1) return 0;
		for(int j = 0; j < n; j ++)
		{
			if(A[i][j] == 3) return 0;
			if(A[i][j])
			{
				unify(i, j);
			}
		}
	}
	for(int i = 0; i < n; i ++)
	{
		mol[par[i]].push_back(i);
	}
	for(int i = 0; i < n; i ++)
	{
		/// the connected component check
		for(auto x : mol[i])
		{
			for(auto y : mol[i])
			{
				if(A[x][y] == 0) return 0;
			}
		}
	}
	for(int i = 0; i < n; i ++) par[i] = i;
	for(int i = 0; i < n; i ++)
	{
		for(auto x : mol[i])
		{
			for(auto y : mol[i])
			{
				if(A[x][y] == 1)
				{
					unify(x, y);
				}
			}
		}
	}
	for(int i = 0; i < n; i ++)
	{
		vec[par[i]].push_back(i);
	}
	for(int i = 0; i < n; i ++)
	{
		for(auto x : vec[i])
		{
			for(auto y : vec[i])
			{
				if(A[x][y] != 1)
				{
					return 0;
				}
			}
		}
		for(int j = 1; j < SZ(vec[i]); j ++)
		{
			add(vec[i][j - 1], vec[i][j]);
		}
	}
	for(int i = 0; i < n; i ++)
	{
		vector < int > cyc;
		for(auto x : mol[i])
		{
			if(x == par[x])
			{
				cyc.push_back(x);
			}
		}
		int sz = SZ(cyc);
		if(sz <= 1) continue;
		for(int j = 0; j < sz; j ++)
		{
			add(cyc[j], cyc[(j + 1) % sz]);
		}
	}
	build(Ans);
	return 1;
}

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