Submission #832198

#	Time	Username	Problem	Language	Result	Execution time	Memory
832198		penguinman	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	190 ms	24012 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;
	};
	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;
		}
	}
	build(ans);
	return 1;
}

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