Submission #301651

#	Time	Username	Problem	Language	Result	Execution time	Memory
301651		Trickster	슈퍼트리 잇기 (IOI20_supertrees)	C++14	21 / 100	316 ms	26236 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 vis[N];
int arr[N][N];
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, int tp)
{
	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] = tp;
}

int construct(vector<vector<int>> p) {
	int 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++) {
			if(i == h) continue;
			
			if(p[i][h] == 1) uni(i, h, 1);

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

	for(int i = 0; i < n; i++)
		for(int h = 0; h < n; h++)
			if(p[i][h] == 2) uni(i, h, 0);
	
	vector <int> E[N];
	for(int i = 0; i < n; i++) E[ata(i)].pb(i);

	for(int i = 0; i < n; i++)
		for(int h = 0; h < n; h++)
			if(p[i][h] == 2) {
				if(sz[ata(i)] == 2) return 0;
				
				if(vis[ata(i)]) continue;
				vis[ata(i)] = 1;

				int last = -1;
				for(auto j: E[ata(i)]) {
					if(last != -1) arr[last][j] = arr[j][last] = 1;
					last = j;
				}
				arr[last][E[ata(i)][0]] = arr[E[ata(i)][0]][last] = 1;
			}

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