제출 #839160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839160		tranxuanbach	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	182 ms	28120 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

const int N = 1e3 + 5;

int n;
vector <vector <int>> cnt_path;

vector <vector <int>> adj;

bool check_clique(const vector <int>& a, int l, int r){
	for (auto u: a){
		for (auto v: a){
			if (u >= v){
				continue;
			}
			if (not (l <= cnt_path[u][v] and cnt_path[u][v] <= r)){
				return false;
			}
		}
	}
	return true;
}

vector <bool> vis;

void dfs(int u, int l, int r, vector <int>& a){
	vis[u] = true;
	a.emplace_back(u);
	for (int v = 0; v < n; v++){
		if (not vis[v] and l <= cnt_path[u][v] and cnt_path[u][v] <= r){
			dfs(v, l, r, a);
		}
	}
}

vector <bool> is_end;

int construct(vector <vector <int>> _p){
	n = isz(_p);
	cnt_path = _p;

	adj.assign(n, vector <int>(n, 0));
	vis.assign(n, false);
	is_end.assign(n, false);

	for (int u = 0; u < n; u++){
		if (vis[u]){
			continue;
		}
		vector <int> a;
		dfs(u, 1, 1, a);
		if (not check_clique(a, 1, 1)){
			return 0;
		}
		for (int i = 0; i + 1 < isz(a); i++){
			int u = a[i], v = a[i + 1];
			adj[u][v] = adj[v][u] = 1;
		}
		is_end[a.back()] = true;
	}

	vis.assign(n, false);
	for (int u = 0; u < n; u++){
		if (vis[u]){
			continue;
		}
		vector <int> a;
		dfs(u, 1, 2, a);
		if (not check_clique(a, 1, 2)){
			return 0;
		}
		vector <int> b;
		for (auto u: a){
			if (is_end[u]){
				b.emplace_back(u);
			}
		}
		if (isz(b) == 1){
			continue;
		}
		if (isz(b) == 2){
			return 0;
		}
		for (int i = 0; i < isz(b); i++){
			int u = b[i], v = b[(i + 1) % isz(b)];
			adj[u][v] = adj[v][u] = 1;
		}
	}

	for (int u = 0; u < n; u++){
		for (int v = 0; v < n; v++){
			if (cnt_path[u][v] == 3){
				return 0;
			}
		}
	}

	build(adj);
	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