Submission #873381

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873381	2023-11-15T01:45:20 Z	bobbilyking	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	0 ms	348 KB

supertrees

#include "supertrees.h"
using namespace std;
#include <bits/stdc++.h>
using ll=long long;

#define F(i, l, r) for (ll i = (l); i < ll(r); ++i)
bool vis[1010];
vector<ll> comp;

struct info {
	vector<ll> twos;
	vector<vector<ll>> ones;
};

vector<info> glob;

void dfs(ll i, vector<vector<int>>& p) {
	if (vis[i]) return;
	vis[i] = 1;
	comp.push_back(i);
	F(j, 0, p.size()) if (p[i][j]) dfs(j, p);
}

ll dsu[1010];
vector<ll> st[1010];
ll find(ll i) {
	return dsu[i] == i ? i: dsu[i] = find(dsu[i]);
}


void my_build(std::vector<std::vector<int>>& b) {
	for (auto &[twos, ones]: glob) {
		for (const auto &y: ones) {
			twos.push_back(y[0]);
			for (ll i = 0; i + 1 < ll(y.size()); ++i) b[y[i]][y[i+1]] = b[y[i+1]][y[i]] = 1;
		}
		F(i, 0, twos.size()) {
			ll nidx = (i+1)%twos.size();
			b[twos[i]][twos[nidx]] = b[twos[nidx]][twos[i]] = 1;
		}
	}
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();

	for (auto &x: p) for (auto y: x) if (y==3) return 0;
	F(i, 0, n) {
		dsu[i] = i;
		st[i] = {i};
	}

	F(i, 0, n) if (!vis[i]) {
		comp.clear();
		dfs(i, p);
		if (comp.size() == 1) continue; // empty live my life yo
		info cur;

		for (auto idx: comp) {
			ll ign = 0;
			for (auto x: comp) if (x-idx) {
				if (!p[idx][x]) return false; // everything within component is connected
				if (p[idx][x] == 1) {
					ll u = find(idx), v = find(x);
					if (u-v) {	
						if (st[u].size() < st[v].size()) swap(u, v);
						dsu[v] = u;
						st[u].insert(st[u].end(), st[v].begin(), st[v].end());
					}
				} else ign++;
			}
			if (ign + 1 == ll(comp.size())) cur.twos.push_back(idx); // all twos
		}

		set<ll> ivis;
		for (auto idx: comp) ivis.insert(find(idx));
		for (auto idx: ivis) {
			for (auto y: st[idx]) for (auto z: st[idx]) if (p[y][z] != 1) return false;
			cur.ones.push_back(st[idx]);
		}

		glob.push_back(cur);
	}	

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

	build(answer);
	return 1;
}

Subtask #1
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	b[0][0] is not 0
3	Halted	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	b[0][0] is not 0
3	Halted	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-