제출 #304048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
304048		eggag32	슈퍼트리 잇기 (IOI20_supertrees)	C++17	21 / 100	263 ms	30200 KiB

supertrees

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int mxN = 1005;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

vector<pi> g[mxN];
int vis[mxN];
vi cur1, cur2;

void dfs1(int cur){
	vis[cur] = 1;
	cur1.pb(cur);
	for(pi x : g[cur]) if(x.se == 1 && !vis[x.fi]) dfs1(x.fi);
}

void dfs2(int cur){
	vis[cur] = 1;
	cur2.pb(cur);
	for(pi x : g[cur]) if(x.se == 2 && !vis[x.fi]) dfs2(x.fi);
}

int construct(vector<vi> p) {
	int n = p.size();
	vector<vi> ans(n);
	rep(i, n) ans[i].resize(n);
	rep(i, n) rep(j, n) ans[i][j] = 0;
	rep(i, n) rep(j, n) if(p[i][j] && i != j){
		g[i].pb({j, p[i][j]});
	}
	rep(i, n){
		int f = 1;
		for(pi x : g[i]){
			if(x.se == 1) f |= 1;
			if(x.se == 2) f |= 2;
		}
		if(f == 3) return 0;
	}
	rep(i, n) if(!vis[i]){
		int f = 1;
		for(pi x : g[i]){
			if(x.se == 1) f |= 1;
			if(x.se == 2) f |= 2;
		}
		if(f == 1){
			cur1.clear();
			dfs1(i);
			int f1 = 1;
			rep(j, cur1.size()) rep(k, cur1.size()) if(j != k){
				if(p[cur1[j]][cur1[k]] != 1){
					f1 = 0;
					break;
				}
			}
			if(!f1) return 0;
			sort(all(cur1));
			rep(j, cur1.size() - 1){
				ans[cur1[j]][cur1[j + 1]] = 1;
				ans[cur1[j + 1]][cur1[j]] = 1;
			}
		}
		if(f == 2){
			cur2.clear();
			dfs2(i);
			int f1 = 1;
			rep(j, cur2.size()) rep(k, cur2.size()) if(j != k){
				if(p[cur2[j]][cur2[k]] != 2){
					f1 = 0;
					break;
				}
			}
			if(!f1 || cur2.size() < 3) return 0;
			sort(all(cur2));
			rep(j, cur2.size() - 1){
				ans[cur2[j]][cur2[j + 1]] = 1;
				ans[cur2[j + 1]][cur2[j]] = 1;
			}
			int m = cur2.size() - 1;
			ans[cur2[0]][cur2[m]] = 1;
			ans[cur2[m]][cur2[0]] = 1;
		}
	}
	build(ans);
	return 1;
}

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