제출 #305084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305084		srvlt	슈퍼트리 잇기 (IOI20_supertrees)	C++14	21 / 100	266 ms	29560 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
#define cps2(x, y) sort(all(x), y), (x).erase(unique(all(x)), end(x))
#define mem(x, y) memset(& x, y, sizeof(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1003;
int n, ans[n0][n0], used[n0], num[n0], k, m, m2, cyc[n0];
bitset <n0> g[n0], has[n0], has2[n0];
string s[n0], s2[n0];
map <string, int> ind, ind2;

int was[n0], good[n0];

void dfs(int v) {
	used[v] = 1, num[v] = k;
	for (int to = 0; to < n; to++) {
		if (used[to] || !g[v][to]) continue;
		dfs(to);
	}
}

int construct(vector<vector<int>> p) {
	n = p.size();
	string emp = "";
	for (int i = 0; i < n; i++) emp += '0';
	for (int i = 0; i < n; i++) {
		s[i] = s2[i] = emp;
		for (int j = 0; j < n; j++) {
			if (p[i][j] >= 1) g[i][j] = 1;
			if (i == j || p[i][j] == 2) s[i][j] = '1';
			s2[i][j] = char('0' + p[i][j]);
		}
		if (!ind.count(s[i])) ind[s[i]] = m++;
		has[ind[s[i]]][i] = 1;
		
		if (!ind2.count(s2[i])) ind2[s2[i]] = m2++;
		has2[ind2[s2[i]]][i] = 1;
	}
	bitset <n0> tmp;
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs(i);
			k++;
			int flag = 0;
			for (int j = 0; j < n; j++) {
				if (num[j] == k - 1) {
					if (!flag) tmp = g[j];
					else if (tmp != g[j]) return 0;
				}
			}
		}
	}
	vector <int> vec;
	for (auto & cur : ind) {
		//cerr << cur.first << ' ' << cur.second << '\n';
		int cnt = 0;
		for (int i = 0; i < n; i++)
			cnt += (cur.first[i] == '1');
		if (cnt == 2) return 0;
		if (cnt == 1) continue;
		vec.clear();
		for (int i = 0; i < n; i++) {
			if (!has[cur.second][i] || cur.first[i] != '1') continue;
			cyc[i] = 1;
			vec.pb(i);
		}
		for (int i = 0; i < SZ(vec); i++) {
			ans[vec[i]][vec[(i + 1) % SZ(vec)]] = 1;
			//cerr << vec[i] << ' ' << vec[(i + 1) % SZ(vec)] << '\n';
		}
	}
	for (auto & cur : ind2) {
		//cerr << cur.first << ' ' << cur.second << '\n';
		int one = -1;
		for (int i = 0; i < n; i++) {
			if (cur.first[i] == '1' && cyc[i]) {
				if (one == -1) one = i;
				else return 0;
			}
		}
		if (one == -1) {
			int cnt = 0, last = -1;
			for (int i = 0; i < n; i++)
				cnt += (cur.first[i] == '1');
			for (int i = 0; i < n; i++) {
				if (!has2[cur.second][i]) continue;
				if (cur.first[i] == '0') return 0;
				cnt--;
				if (last == -1) last = i;
				else {
					ans[last][i] = 1;
				}
			}
			if (cnt != 0) return 0;
			continue;
		}
		int flag = 0;
		for (int i = 0; i < n; i++) {
			if (!has2[cur.second][i]) continue;
			if (one != i) flag = 1;
		}
		if (!flag) continue;
		if (was[one]) return 0;
		was[one] = 1;
		
		mem(good, 0);
		good[one] = 1;
		for (int i = 0; i < n; i++) {
			if (!has2[cur.second][i]) continue;
			if (cur.first[i] != '1') return 0;
			ans[one][i] = 1;
			good[i] = 1;
		}
		for (int i = 0; i < n; i++) {
			if (good[i]) continue;
			if (cur.first[i] != '0' && num[i] != num[one]) return 0;
			if (cur.first[i] != '2' && num[i] == num[one]) return 0;
		}
	}
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		for (int j = 0; j < n; j++)
			if (ans[i][j] || ans[j][i]) row[j] = 1;
		answer.push_back(row);
	}
	build(answer);
	return 1;
}

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