Submission #301898

#	Time	Username	Problem	Language	Result	Execution time	Memory
301898		Trickster	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	293 ms	30264 KiB

supertrees

#include "supertrees.h"
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define N 1010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n, ans;
int vis[N];
int vis2[N];
int vis3[N];
int arr[N][N];
int pat[N][N];
vector <int> E;
int P[N], sz[N];

int ata(int x)
{
	if(x == P[x]) return x;

	return P[x] = ata(P[x]);
}

void uni(int a, int b)
{
	a = ata(a);
	b = ata(b);

	if(a == b) return;

	if(sz[a] < sz[b]) swap(a, b);

	P[b] = a, sz[a] += sz[b], sz[b] = 0;
	
	arr[a][b] = arr[b][a] = 1;
}

void dfs(int nd)
{
	E.pb(nd);
	vis[nd] = 1;

	for(int i = 0; i < n; i++) if(i != nd) vis2[i] = (pat[nd][i] != 2 ? 0 : vis2[i]);

	for(int i = 0; i < n; i++)
		if(pat[nd][i] == 2 && !vis[i]) {
			if(vis2[i] == 0) {
				ans = 1;
				return;
			}
			dfs(i);
			return;
		}
}

int construct(vector<vector<int>> p) {
	n = p.size();

	for(int i = 0; i < n; i++) P[i] = i, sz[i] = 1;

	for(int i = 0; i < n; i++)
		for(int h = 0; h < n; h++) {
			pat[i][h] = p[i][h];
			
			if(p[i][h] == 3) return 0;
		}
	
	for(int i = 0; i < n; i++) {
		if(vis[i]) continue;

		E.clear();
		memset(vis2, 0, sizeof(vis2));
		for(int h = 0; h < n; h++) vis2[h] = (p[i][h] == 2 ? 1 : 0);

		dfs(i);

		if(ans == 1 || E.size() == 2) return 0;

		int last = -1;
		for(auto h: E) {
			if(last != -1) arr[last][h] = arr[h][last] = 1;

			last = h;
			vis3[h] = 1;
			for(int j = 0; j < n; j++)
				if(p[h][j] == 1 && h != j) {
					if(ata(j) == ata(h)) continue;

					if(vis3[j] == 1) return 0;
					vis3[j] = 1;
					uni(h, j);
				}
		}

		if(E.size() == 1) continue;

		arr[E[0]][last] = arr[last][E[0]] = 1;
	}

	for(int i = 0; i < n; i++)
		for(int h = 0; h < n; h++)
			if(!p[i][h] && ata(i) == ata(h)) return 0;

	vector <vector <int>> ret;
	ret.resize(n);
	for(int i = 0; i < n; i++)
		for(int h = 0; h < n; h++)
			ret[i].pb(arr[i][h]);
	
	build(ret);
	return 1;
}

Compilation message (stderr)

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

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