Submission #301989

#	Time	Username	Problem	Language	Result	Execution time	Memory
301989		Trickster	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	282 ms	30328 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 P[N];
int n, ans;
int arr[N][N];
int pat[N][N];
vector <int> E;
int vis[N], vis2[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;

	P[b] = a;
	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) {
		if(pat[nd][i] == 1) vis2[i] = (vis2[i] == 1 ? 2 : vis2[i]);
		if(pat[nd][i] == 0) vis2[i] = 0;
	}

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

	for(int i = 0; i < n; i++) {
		if(ata(i) == ata(nd)) continue;

		if(pat[nd][i] == 1) {
			if(vis[i] == 1) {
				ans = 1;
				return;
			}
			uni(nd, i);
			upd(i);
		}
	}
}

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

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

	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++) {
			if(i == h) continue;
			if(p[i][h] == 1) vis2[h] = 2;
			if(p[i][h] == 2) vis2[h] = 1;
		}

		dfs(i);

		if(E.size() == 2) return 0;

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

			upd(h);
			last = h;
		}
		if(E.size() == 1) continue;

		arr[E[0]][last] = arr[last][E[0]] = 1;
	}
	if(ans == 1) return 0;

	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: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4