Submission #1177943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177943		browntoad	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	124 ms	22288 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

const ll maxn = 1e3+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;

int par[maxn][2];

int fin(int a, bool wh){
	if (par[a][wh] == a) return a;
	return par[a][wh] = fin(par[a][wh], wh);
}
void merg(int a, int b, bool wh){
	a = fin(a, wh); b = fin(b, wh);
	if (a == b) return;
	par[a][wh] = b;
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	REP(i, n) par[i][0] = par[i][1] = i;
	REP(i, n){
		REP(j, n){
			if (i == j && p[i][j] != 1) return 0;
			if (p[i][j] == 3) return 0;
			if (i != j && p[i][j] >= 1){
				merg(i, j, 0);
			}
		}
	}

	REP(i, n){
		REP(j, n){
			bool p1 = (fin(i, 0) == fin(j, 0));
			if (p1 != (p[i][j] >= 1)) return 0;
		}
	}
	vector<vector<int>> comps(n);
	REP(i, n) comps[fin(i, 0)].pb(i);

	vector<vector<int>> trecomps(n);
	for (auto vv:comps){
		if (SZ(vv) == 0) continue;
		int m = SZ(vv);
		REP(i, m){
			FOR(j, i+1, m){
				if (p[vv[i]][vv[j]] == 1) merg(vv[i], vv[j], 1);
			}
		}
		REP(i, m) FOR(j, i+1, m) if ((p[vv[i]][vv[j]] == 1) != (fin(vv[i], 1) == fin(vv[j], 1))) return 0;

		REP(i, m){
			trecomps[fin(vv[i], 1)].pb(vv[i]);
		}
		vector<vector<int>> trees;
		REP(i, m) if (SZ(trecomps[vv[i]]) >= 1) trees.pb(trecomps[vv[i]]);

		if (SZ(trees) == 2) return 0;
		int lstid = -1;
		for (auto tree:trees){
			if (lstid != -1){
				answer[tree[0]][lstid] = answer[lstid][tree[0]] = 1;
			}
			lstid = tree[0];
			int lsttreeid = -1;
			for (auto v:tree){
				if (lsttreeid != -1) answer[lsttreeid][v] = answer[v][lsttreeid] = 1;
				lsttreeid = v;
			}
		}
		if (SZ(trees) > 1){
			answer[trees[0][0]][lstid] = answer[lstid][trees[0][0]] = 1;
		}
	}
	build(answer);
	return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 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