Submission #1183038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183038		trvhung	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	125 ms	34136 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int maxn = 1e3 + 5;
int n, a[maxn][maxn], id[maxn], cc, bel[maxn];
vector<int> adj[maxn], edgeTree[maxn], vec[maxn];
vector<vector<int>> b;
bool vis[maxn], inCyc[maxn];

void dfs_cc(int u) {
	id[u] = cc; vec[cc].push_back(u);
	for (int v: adj[u])
		if (!id[v])
			dfs_cc(v);
}

void dfs(int u, int par, int rt) {
	vis[u] = true; 
	bel[u] = rt;

	for (int v: edgeTree[u])
		if (v != par && !vis[v]) {
			b[u - 1][v - 1] = b[v - 1][u - 1] = 1;
			dfs(v, u, rt);
		}
}

bool sub_proc(int c, int deg) {
	vector<int> cyc;
	for (int i: vec[c])
		if (!vis[i]) {
			inCyc[i] = true;
			cyc.push_back(i);
			dfs(i, 0, i);
		}

	if ((int) cyc.size() < deg + 1) return false;
	b[cyc.back() - 1][cyc[0] - 1] = b[cyc[0] - 1][cyc.back() - 1] = 1;
	if (deg == 3) b[cyc[0] - 1][cyc[2] - 1] = b[cyc[2] - 1][cyc[0] - 1] = 1;
	for (int i = 0; i < (int) cyc.size() - 1; ++i)
		b[cyc[i] - 1][cyc[i + 1] - 1] = b[cyc[i + 1] - 1][cyc[i] - 1] = 1;

	for (int i: vec[c]) {
		if (inCyc[i]) {
			for (int j: vec[c]) 
				if (inCyc[j] && a[i][j] != (i == j ? 1 : deg)) 
					return false;
				else if (!inCyc[j]) {
					if (bel[j] != i && a[i][j] != deg) return false;
					else if (bel[j] == i && a[i][j] != 1) return false;
				}
		} else {
			for (int j: vec[c])
				if (inCyc[j]) {
					if (j == bel[i] && a[i][j] != 1) return false;
					else if (j != bel[i] && a[i][j] != deg) return false;
				} else {
					if (bel[i] == bel[j] && a[i][j] != 1) return false;
					else if (bel[i] != bel[j] && a[i][j] != deg) return false;
				}
		}
	}

	return true;
}

bool process(int c) {
	bool have2 = false, have3 = false;
	for (int i: vec[c])
		for (int j = 1; j <= n; ++j) {
			have2 |= a[i][j] == 2;
			have3 |= a[i][j] == 3;
		}	

	if (have2 && have3) return false;
	if (!have2 && !have3) return dfs(vec[c][0], 0, vec[c][0]), true;
	return (have2 ? sub_proc(c, 2) : sub_proc(c, 3));
}
 	
#ifdef trvhung
void build(vector<vector<int>> b) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			cout << b[i][j] << ' ';
		cout << el;
	}
}
#endif

int construct(vector<vector<int>> p) {
	n = (int) p.size(); 
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) {
			a[i][j] = p[i - 1][j - 1];
			if (a[i][j] == 3) return 0;
		}

	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= n; ++j) {
			if (a[i][j] > 0)
				adj[i].push_back(j);
			if (a[i][j] == 1 && i != j)
				edgeTree[i].push_back(j);
		}

	for (int i = 1; i <= n; ++i)
		if (!id[i]) {
			cc++;
			dfs_cc(i);
		}

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (a[i][j] == 0 && id[i] == id[j])
				return 0;

	b.resize(n);
	for (int i = 0; i < n; ++i) b[i].resize(n);

	for (int i = 1; i <= cc; ++i)
		if (!process(i))
			return 0;

	build(b);

	return 1;
}

#ifdef trvhung
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.inp", "r", stdin);
    freopen("output.out", "w", stdout);
    #endif

    int n;
    vector<vector<int>> v;

    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i) {
    	v[i].resize(n);
    	for (int j = 0; j < n; ++j)
    		cin >> v[i][j];
    }

    cout << construct(v);

    return 0;
}
#endif

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