Submission #832211

#	Time	Username	Problem	Language	Result	Execution time	Memory
832211		penguinman	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	233 ms	24020 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

int construct(std::vector<std::vector<int>> p) {
	int N = p.size();
	vector<vector<int>> ans(N, vector<int>(N));
	vector<bool> flag(N);
	auto tree = [&](vi v){
		rep(i,1,v.size()){
			ans[v[i-1]][v[i]] = ans[v[i]][v[i-1]] = 1;
		}
		rep(i,0,v.size()){
			rep(j,i+1,v.size()){
				if(p[v[i]][v[j]] != 1) return true;
			}
		}
		return false;
	};
	auto loop = [&](vi v){
		if(v.size() == 2) return true;
		rep(i,0,v.size()){
			ans[v[(i+1)%v.size()]][v[i]] = ans[v[i]][v[(i+1)%v.size()]] = 1;
		}
		rep(i,0,v.size()){
			rep(j,i+1,v.size()){
				if(p[v[i]][v[j]] != 2) return true;
			}
		}
		return false;
	};
	vector<bool> mem_flag(N);
	rep(i,0,N){
		if(flag[i]) continue;
		flag[i] = true;
		std::queue<ll> que;
		que.push(i);
		vi v;
		while(!que.empty()){
			ll now = que.front(); que.pop();
			v.pb(now);
			rep(next, 0, N){
				if(p[now][next]){
					if(!flag[next]){
						flag[next] = true;
						que.push(next);
					}
				}
			}
		}
		vi cnt(4);
		for(auto el: v){
			rep(j,0,N){
				if(el == j) continue;
				cnt[p[el][j]]++;
			}
		}
		if(cnt[2] == 0){
			if(tree(v)) return 0;
			continue;
		}
		if(cnt[1] == 0){
			if(loop(v)) return 0;
			continue;
		}
		vector<pii> data;
		for(auto el: v){
			ll cnt = 0;
			rep(j,0,N){
				if(el == j) continue;
				if(p[el][j] == 1) cnt++;
			}
			data.pb(mp(cnt, el));
		}
		sort(all(data));
		reverse(all(data));
		vi par;
		vii member;
		for(auto el: data){
			if(mem_flag[el.second]) continue;
			mem_flag[el.second] = true;
			vi mb;
			par.pb(el.second);
			rep(j,0,N){
				if(el.second == j) continue;
				if(p[el.second][j] == 1){
					mb.pb(j);
					if(mem_flag[j]) return 0;
					mem_flag[j] = true;
				}
			}
			member.pb(mb);
		}
		if(par.size() <= 2) return 0;
		rep(j,0,par.size()){
			ans[par[j]][par[(j+1)%par.size()]] = ans[par[(j+1)%par.size()]][par[j]] = 1;
		}
		rep(j,0,par.size()){
			for(auto el: member[j]) ans[par[j]][el] = ans[el][par[j]] = 1;
		}
		rep(j,0,par.size()){
			rep(k,j+1,par.size()){
				if(p[par[j]][par[k]] != 2) return 0;
				for(auto el1: member[j]){
					for(auto el2: member[k]){
						if(p[el1][el2] != 2) return 0;
					}
				}
			}
			for(auto el1: member[j]){
				for(auto el2: member[j]){
					if(el1 == el2) continue;
					if(p[el1][el2] != 1) return 0;
				}
			}
		}
	}
	build(ans);
	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