Submission #822988

#	Time	Username	Problem	Language	Result	Execution time	Memory
822988		ymm	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	244 ms	24180 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

vector<vector<int>> ans;
int n;

struct dsu {
	vector<int> par;
	vector<vector<int>> nds;
	void init(int n) { 
		par.assign(n, -1);
		nds.assign(n, vector<int>());
		Loop (i,0,n)
			nds[i].push_back(i);
	}
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool same(int v, int u) { return rt(v) == rt(u); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		if (nds[v].size() < nds[u].size())
			swap(v, u);
		par[u] = v;
		nds[v].insert(nds[v].end(), nds[u].begin(), nds[u].end());
		vector<int> tmp;
		tmp.swap(nds[u]);
		return 1;
	}
};

int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	ans.assign(n, vector<int>(n, 0));
	Loop (i,0,n) Loop (j,i+1,n) {
		if (p[i][j] == 3)
			return 0;
	}
	dsu dsu1;
	dsu1.init(n);
	Loop (i,0,n) Loop (j,i+1,n) {
		if (p[i][j] == 1 && dsu1.unite(i, j))
			ans[i][j] = ans[j][i] = 1;
	}
	Loop (i,0,n) Loop (j,i+1,n) {
		if (p[i][j] != 1 && dsu1.same(i, j))
			return 0;
	}
	dsu dsu2;
	dsu2.init(n);
	Loop (i,0,n) Loop (j,i+1,n) {
		if (p[i][j] != 2)
			continue;
		if (dsu1.same(i, j))
			return 0;
		int x = dsu1.rt(i);
		int y = dsu1.rt(j);
		dsu2.unite(x, y);
	}
	Loop (i,0,n) Loop (j,i+1,n) {
		int x = dsu1.rt(i);
		int y = dsu1.rt(j);
		if (p[i][j] == 0 && dsu2.same(x, y))
			return 0;
	}
	Loop (i,0,n) {
		if (dsu2.par[i] != -1)
			continue;
		int sz = dsu2.nds[i].size();
		if (sz <= 1)
			continue;
		if (sz == 2)
			return 0;
		Loop (j,0,sz) {
			int x = dsu2.nds[i][j];
			int y = dsu2.nds[i][(j+1)%sz];
			ans[x][y] = ans[y][x] = 1;
		}
	}
	build(ans);
	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