제출 #1225347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225347		Nonoze	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	127 ms	22284 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define fi first
#define se secod
#define sz(x) (int)x.size()
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back

using namespace std;

int n;
vector<int> par, sz;

int getpar(int x) {
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}

bool same(int a, int b) {
	return getpar(a)==getpar(b);
}

bool unite(int a, int b) {
	a=getpar(a), b=getpar(b);
	if (a==b) return 1;
	if (sz[a]<sz[b]) swap(a, b);
	sz[a]+=sz[b], par[b]=a;
	return 1;
}

int construct(vector<vector<int>> base) {
	n = sz(base);
	par.resize(n), sz.resize(n, 1); iota(all(par), 0);
	vector<vector<int>> answer(n, vector<int>(n, 0));
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			if (base[i][j] && !unite(i, j)) return 0;
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (!base[i][j] && same(i, j)) return 0;
		}
	}
	vector<vector<int>> vec(n);
	for (int i=0; i<n; i++) {
		vec[getpar(i)].pb(i);
	}
	for (auto compo: vec) if (sz(compo)>1) {
		int m=sz(compo);
		vector<vector<int>> p(m, vector<int>(m));
		for (int i=0; i<m; i++) {
			for (int j=0; j<m; j++) {
				p[i][j]=base[compo[i]][compo[j]];
			}
		}
		vector<vector<int>> isin1(m), isin2(m);
		vector<bool> used1(m, 0);
		for (int i=0; i<m; i++) if (!used1[i]) {
			vector<int> vec;
			for (int j=i; j<m; j++) {
				if (p[i][j]==1) vec.pb(j);
			}
			if (sz(vec)>1) {
				for (auto &u: vec) used1[u]=1, isin1[i].pb(u);
				for (int j=1; j<sz(vec); j++) {
					answer[compo[vec[j-1]]][compo[vec[j]]]=answer[compo[vec[j]]][compo[vec[j-1]]]=1;
				}
				for (int j=0; j<sz(vec); j++) {
					for (int k=j+1; k<sz(vec); k++) {
						if (p[vec[j]][vec[k]]!=1) return 0;
					}
				}
				used1[i]=0;
			} else isin1[i].pb(i);
		}
		vector<bool> used2(m, 0);
		for (int i=0; i<m; i++) if (!used2[i] && !used1[i]) {
			vector<int> vec(1, i);
			for (int j=i; j<m; j++) {
				if (p[i][j]==2 && !used1[j]) vec.pb(j);
			}
			if (sz(vec)>1) {
				if (sz(vec)==2) return 0;
				for (auto &u: vec) used2[u]=1;
				for (int j=0; j<sz(vec); j++) {
					answer[compo[vec[(j+1)%sz(vec)]]][compo[vec[j]]]=answer[compo[vec[j]]][compo[vec[(j+1)%sz(vec)]]]=1;
				}
				for (int j=0; j<sz(vec); j++) {
					for (int k=j+1; k<sz(vec); k++) {
						for (auto x: isin1[vec[j]]) for (auto y: isin1[vec[k]]) if (p[x][y]!=2) return 0;
					}
					for (auto x: isin1[j]) isin2[i].pb(x);
				}
				used2[i]=0;
			} else isin2[i].pb(i);
		}
		vector<bool> used3(m, 0);
		for (int i=0; i<m; i++) if (!used3[i] && !used2[i] && !used1[i]) {
			vector<int> vec(1, i);
			for (int j=i; j<m; j++) {
				if (p[i][j]==3 && !used1[j] && !used2[j]) vec.pb(j);
			}
			if (sz(vec)>1) {
				if (sz(vec)<=3) return 0;
				for (auto &u: vec) used3[u]=1;
				for (int j=0; j<sz(vec); j++) {
					answer[compo[vec[(j+1)%sz(vec)]]][compo[vec[j]]]=answer[compo[vec[j]]][compo[vec[(j+1)%sz(vec)]]]=1;
				}
				answer[compo[vec[0]]][compo[vec[sz(vec)-2]]]=answer[compo[vec[sz(vec)-2]]][compo[vec[0]]]=1;
				for (int j=0; j<sz(vec); j++) {
					for (int k=j+1; k<sz(vec); k++) {
						for (auto x: isin1[vec[j]]) for (auto y: isin1[vec[k]]) if (p[x][y]!=2) return 0;
					}
					for (auto x: isin1[j]) isin2[i].pb(x);
				}
				used3[i]=0;
			}
		}
		// vector<int> vec;
		// for (int i=0; i<m; i++) {
		// 	if (!used1[i] && !used2[i]) {
		// 		vec.pb(i);
		// 	}
		// }
		// if (sz(vec)<=1) continue;
		// if (sz(vec)<=3) return 0;
		// for (int i=0; i<sz(vec); i++) {
		// 	answer[compo[vec[(i+1)%sz(vec)]]][compo[vec[i]]]=answer[compo[vec[i]]][compo[vec[(i+1)%sz(vec)]]]=1;
		// }
		// answer[compo[vec[0]]][compo[vec[sz(vec)-2]]]=answer[compo[vec[sz(vec)-2]]][compo[vec[0]]]=1;
		// for (int j=0; j<sz(vec); j++) {
		// 	for (int k=j+1; k<sz(vec); k++) {
		// 		if (sz(isin2[vec[j]])>1 || sz(isin2[vec[k]])>1) return 0;
		// 		for (auto x: isin1[vec[j]]) for (auto y: isin1[vec[k]]) if (p[x][y]!=3) return 0;
		// 	}
		// }
	}
	vector<vector<int>> adj(n);
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (answer[i][j]) adj[i].pb(j);
		}
	}
	build(answer);
	return 1;
}

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