Submission #300203

#	Time	Username	Problem	Language	Result	Execution time	Memory
300203		Gajowy	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	275 ms	22264 KiB

supertrees

#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include "supertrees.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint uint_fast64_t
#define ll int_fast64_t
#define ull uint_fast64_t
#define int16 int_fast16_t
#define uint16 uint_fast16_t
#define int32 int_fast32_t
#define uint32 uint_fast32_t
#define int64 int_fast64_t
#define uint64 uint_fast64_t
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define rall(r) rbegin(r),rend(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#define elapsed(__begin,__end) (__end-__begin)/CLOCKS_PER_SEC
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;

const int MAXN=1e3+10;

bool vis[MAXN],vis2[MAXN];
vector<int> cmp;
int rep[MAXN],sz[MAXN],col[MAXN],cols=0;

void dfs(int u,vector<vector<int>> &g)
{
	vis[u]=true;
	cmp.eb(u);
	for(int v=0;v<size(g);v++)
		if(!vis[v]&&g[u][v]==1)
			dfs(v,g);
}

int fnd(int u)
{
	return (rep[u]==u?u:rep[u]=fnd(rep[u]));
}

void dfs2(int u,vector<vector<int>> &g)
{
	vis[u]=true;
	col[u]=cols;
	if(!vis2[fnd(u)])
		vis2[fnd(u)]=true,cmp.eb(fnd(u));
	for(int v=0;v<size(g);v++)
		if(!vis[v]&&g[u][v])
			dfs2(v,g);
}

bool onion(int u,int v)
{
	u=fnd(u),v=fnd(v);
	if(u==v)
		return false;
	if(sz[v]>sz[u])
		swap(u,v);
	sz[u]+=sz[v];
	rep[v]=u;
	return true;
}

int construct(vector<vector<int>> g)
{
	int n=size(g);
	vector<vector<int>> res(n,vector<int>(n,0));
	for(int i=1;i<=n;i++)
		rep[i]=i,sz[i]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(g[i][j]==3)
				return 0;
	for(int i=0;i<n;i++)
		if(!vis[i])
		{
			cmp.clear();
			dfs(i,g);
			if(size(cmp)==1)
				continue;
			for(auto u:cmp)
				for(auto v:cmp)
					if(u!=v&&g[u][v]!=1)
						return 0;
			for(int i=1;i<size(cmp);i++)
				if(onion(cmp[i-1],cmp[i]))
					res[cmp[i-1]][cmp[i]]=res[cmp[i]][cmp[i-1]]=1;
		}
	for(int i=0;i<n;i++)
		vis[i]=false;
	for(int i=0;i<n;i++)
		if(!vis[i])
		{
			cmp.clear();
			cols++;
			dfs2(i,g);
			if(size(cmp)==1)
				continue;
			if(size(cmp)==2)
				return 0;
			for(int i=1;i<size(cmp);i++)
				res[cmp[i-1]][cmp[i]]=res[cmp[i]][cmp[i-1]]=1;
			res[cmp.back()][cmp[0]]=res[cmp[0]][cmp.back()]=1;
		}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(col[i]==col[j])
			{
				if(fnd(i)==fnd(j))
				{
					if(g[i][j]!=1)
						return 0;
				}
				else
				{
					if(g[i][j]!=2)
						return 0;
				}
			}
			else
			if(g[i][j])
				return 0;
	build(res);
	return 1;
}

Compilation message (stderr)

supertrees.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
supertrees.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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