Submission #998117

#	Time	Username	Problem	Language	Result	Execution time	Memory
998117		Arapak	Comparing Plants (IOI20_plants)	C++17	Compilation error	0 ms	0 KiB

plants

// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename F, typename S> ostream& operator<<(ostream& os, const pair<F, S> &p) { return os<<"("<<p.first<<", "<<p.second<<")"; }
template<typename T> ostream &operator<<(ostream & os, const vector<T> &v) { os << "{"; typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) { if( it != v.begin() ) os << ", "; os << *it; } return os << "}"; }

void dbg_out() { cerr<<'\n'; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr<<' '<<H; dbg_out(T...); }

#ifdef DEBUG
#define dbg(...) cerr<<"(" << #__VA_ARGS__ <<"):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 
#endif

struct DSU {
	vi dsu, siz;

	DSU(int n) : dsu(n), siz(n, 1) {
		iota(all(dsu), 0);
	}

	int find(int x) {
		if(dsu[x] == x) return x;
		return dsu[x] = find(dsu[x]);
	}

	void merge(int a, int b) {
		a = find(a); b = find(b);
		if(a == b) return;
		if(siz[a] < siz[b]) swap(a, b);
		else if(siz[a] == siz[b]) siz[a]++;
		dsu[b] = a;
	}

	bool same(int a, int b) {
		return find(a) == find(b);
	}
};

int n;
vector<vi> answer;

pair<bool, vi> find_connected(vector<vi> &p) {
	DSU dsu(n);
	rep(i,0,n) rep(j,0,n) 
		if(p[i][j] > 0) dsu.merge(i, j);

	rep(i,0,n) rep(j,0,n)
		if(p[i][j] == 0 && dsu.same(i, j))
			return {false, {}};
	return {true, dsu.dsu}; 
}

pair<bool, vi> find_one_connected(vector<vi> &p) {
	DSU dsu(n);
	rep(i,0,n) rep(j,0,n) 
		if(p[i][j] == 1) dsu.merge(i, j);

	rep(i,0,n) rep(j,0,n)
		if(p[i][j] != 1 && dsu.same(i, j))
			return {false, {}};
	return {true, dsu.dsu}; 
}

int construct(vector<vi> p) {
	n = p.size();
	answer.assign(n, vi(n, 0));
	auto [correct, conn] = find_connected(p);
	if(!correct) return 0;

	auto [one_correct, one_conn] = find_one_connected(p);
	if(!one_correct) return 0;

	rep(i,0,n) {
		if(one_conn[i] == i) continue;
		answer[i][one_conn[i]] = 1;
		answer[one_conn[i]][i] = 1;
	}

	vector<vi> cycles(n);
	rep(i,0,n) if(one_conn[i] == i) 
		cycles[conn[i]].push_back(i);

	rep(i,0,n)
		rep(j,1,sz(cycles[i])) {
			answer[cycles[i][j]][cycles[i][j-1]] = true;
			answer[cycles[i][j-1]][cycles[i][j]] = true;
		}

	build(answer);
	return 1;
}

Compilation message (stderr)

plants.cpp:3:10: fatal error: supertrees.h: No such file or directory
    3 | #include "supertrees.h"
      |          ^~~~~~~~~~~~~~
compilation terminated.