제출 #419751

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

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void road(vector <vector<int> >&ans, int a, int b) {
	ans[a][b] = ans[b][a] = 1;
}
int n;
const int N = 1e3 + 5;
vector <int> par(N);
// vector <vector <int> > par(N);
int find(int a) {
	if (par[a] == a) return a;
	return par[a] = find(par[a]);
}
bool merge(int a, int b, vector <vector<int> >& p) {
	int A = find(a), B = find(b);
	par[B] = A;
	// cout << a << ' ' << b << " " << A << ' ' << B << '\n';
	p[A][B] = p[B][A] = 2;
	// cout << "A: ";
	// for (auto el : p[A]) cout << el << ' ';
	// cout << "\n";
	// cout << "B: ";
	// for (auto el : p[B]) cout << el << ' ';
	// cout << "\n";
	if (p[A] != p[B]) return 0;
	for (int i = 0; i < n; i++) {
		if (p[B][i] > 0) p[B][i] = p[i][B] = 0;
	}
	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < n; j++) cout << p[i][j] << ' ';
	// 	cout << "\n";
	// }
	return 1;
}
int construct(vector <vector<int> > p) {
	n = p.size();
	vector <vector <int> > answer(n, vector <int>(n, 0)), paths(n);
	for (int i = 0; i < n; i++) par[i] = i, p[i][i] = 2;
	// cout << "HERE\n";

	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++) {
		if (p[i][j] == 3) return 0;
	}
	// cout << "HERE\n";
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 1) {
				if (!merge(i, j, p)) {
					return 0;
				}
				road(answer, i, j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 2) {
				paths[i].push_back(j);
			}
		}
	}

	vector <bool> vis(n+5, 0);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		vector <int> child, tmp;
		for (auto el : paths[i]) child.push_back(el);
		while(child.size() > 1) {
			if (child.size() & 1) child.push_back(child.back());
			tmp.clear();;
			int k = child.size();
			for (int j = 0; j < k; j+=2) {
				if (paths[child[j]] != paths[child[j+1]]) {
					return 0;
				}
				tmp.push_back(child[j]);
			}
			swap(child, tmp);
		}
		child.clear();
		for (auto el : paths[i]) child.push_back(el);

		// cout << i << ": ";
		// for (auto el : child) cout << el << ' ';
		// cout << '\n';
		int m = paths[i].size();
		if (m == 2) return 0;
		for (int j = 0; j < m; j++) {
			vis[child[j]] = 1;
			road(answer, child[j], child[(j+1)%m]);
		}
	}
	for (int i = 0; i < n; i++) answer[i][i] = 0;
	build(answer);
	return 1;
}

// g++ -std=gnu++17 -O2 -Wall -pipe -static -o supertrees grader.cpp supertrees.cpp

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