제출 #1290172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290172		blackscreen1	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	105 ms	22288 KiB

supertrees

#include "supertrees.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i < h; i += g)
#define jloop_(m, h, g) for (auto j = m; j < h; j += g)
#define kloop_(m, h, g) for (auto k = m; k < h; k += g)
#define lloop_(m, h, g) for (auto l = m; l < h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll par[1005], note[1005];
ll par2[1005], t[1005];
vector<ll> v[1005], v2[1005];
vector<ll> anc;
bool yes = 1;
ll find(ll x) {
	return (par[x] == x ? x : par[x] = find(par[x]));
}
void merge(ll x, ll y) {
	par[find(x)] = find(y);
}
ll find2(ll x) {
	return (par2[x] == x ? x : par2[x] = find2(par2[x]));
}
void merge2(ll x, ll y) {
	par2[find2(x)] = find2(y);
}
int construct(vector<vector<int>> p) {
	anc.clear();
	ll n = p.size();
	iloop(0, n) jloop(0, n) if (p[i][j] == 3) return 0;
	iloop(0, n) if (p[i][i] != 1) return 0;
	iloop(0, n) par[i] = par2[i] = i, t[i] = 6;
	iloop(0, n) {
		jloop(0, n) if (p[i][j] == 1) merge(i, j);
	}
	iloop(0, n) v[find(i)].push_back(i);
	iloop(0, n) if (v[i].size()) anc.push_back(i);
	//iloop(0, n) cout << find(i);
	for (auto i : anc) jloop(0, (ll)v[i].size()) kloop(j+1, (ll)v[i].size()) if (p[v[i][j]][v[i][k]] != 1) yes = 0;
	//cout << yes << "\n";
	iloop(0, (ll)anc.size()) jloop(i+1, (ll)anc.size()) if (p[anc[i]][anc[j]] >= 2) {
		if (t[find2(anc[i])]%p[anc[i]][anc[j]] != 0 || t[find2(anc[j])]%p[anc[i]][anc[j]] != 0) {yes = 0; continue;}
		t[find2(anc[i])] = t[find2(anc[j])] = p[anc[i]][anc[j]];
		merge2(anc[i], anc[j]);
	}
	//cout << yes << "\n";
	iloop(0, (ll)anc.size()) v2[find2(anc[i])].push_back(anc[i]);
	//iloop(0, (ll)anc.size()) {cout << anc[i] << " " << find2(anc[i]) << " " << t[anc[i]] << " " << v2[anc[i]].size() << "\n";}
	iloop(0, (ll)anc.size()) if (find2(anc[i]) == anc[i] && t[anc[i]] != 6 && t[anc[i]] + 1 > (ll)v2[anc[i]].size()) yes = 0;
	//cout << yes << "\n";
	vector<vector<int>> res;
	vector<int> zero;
	iloop(0, n) zero.push_back(0);
	iloop(0, n) res.push_back(zero);
	iloop(0, (ll)anc.size()) if (find2(anc[i]) == anc[i]) jloop(0, (ll)v2[anc[i]].size()) kloop(j+1, (ll)v2[anc[i]].size()) if (p[v2[anc[i]][j]][v2[anc[i]][k]] != t[anc[i]]) yes = 0;
	iloop(0, (ll)anc.size()) jloop(i+1, (ll)anc.size()) if (p[anc[i]][anc[j]] >= 2) for (auto it : v[anc[i]]) for (auto it2 : v[anc[j]]) if (p[anc[i]][anc[j]] != p[it][it2]) {yes = 0; continue;}
	if (yes == 0) return 0;
	iloop(0, (ll)anc.size()) jloop(0, (ll)v[anc[i]].size() - 1) res[v[anc[i]][j]][v[anc[i]][j+1]] = res[v[anc[i]][j+1]][v[anc[i]][j]] = 1;
	//iloop(0, n) {jloop(0, n) {cout << res[i][j];} cout << "\n";}
	iloop(0, (ll)anc.size()) if (v2[anc[i]].size()) {
		jloop(0, (ll)v2[anc[i]].size() - 1) res[v2[anc[i]][j]][v2[anc[i]][j+1]] = res[v2[anc[i]][j+1]][v2[anc[i]][j]] = 1;
		if ((ll)v2[anc[i]].size() > 1) res[v2[anc[i]][0]][v2[anc[i]][(ll)v2[anc[i]].size() - 1]] = res[v2[anc[i]][(ll)v2[anc[i]].size() - 1]][v2[anc[i]][0]] = 1;
		if (t[anc[i]] == 3) res[v2[anc[i]][0]][v2[anc[i]][2]] = res[v2[anc[i]][2]][v2[anc[i]][0]] = 1;
	}
	//iloop(0, n) {jloop(0, n) {cout << res[i][j];} cout << "\n";}
	//iloop(0, n) res[i][i] = 0;
	build(res);
	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