Submission #573545

#	Time	Username	Problem	Language	Result	Execution time	Memory
573545		fuad27	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	213 ms	24032 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool same_set(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return true;
	}
};
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<int> cycle[n+1];
	vector<vector<int>> ans(n, vector<int> (n));
	DSU dsu = DSU(n);
	for(int i = 0;i<n;i++) {
		for(int j = 0;j<n;j++) {
			if(p[i][j] == 3 or p[i][j]!=p[j][i])return 0;
			if(p[i][j]==1)dsu.unite(i,j);
		}
	}
	for(int i = 0;i<n;i++)
		for(int j = 0;j<n;j++)
			if(p[i][j]!=p[dsu.get(i)][dsu.get(j)])return 0;
	vector<int> trees;
	for(int i = 0;i<n;i++) {
		int c = dsu.get(i);
		if(c == i)
			trees.push_back(i);
		else ans[i][c]=ans[c][i]=1;
	}
	dsu = DSU(n);
	for(int i:trees) {
		for(int j:trees) {
			if(p[i][j]==2)dsu.unite(i,j);
		}
	}
	for(int i:trees) {
		if(2<=(int)dsu.size(i)) {
			cycle[dsu.get(i)].push_back(i);
		}
	}
	for(int i = 0;i < n;i++) {
		if(!cycle[i].size())continue;
		if((int)cycle[i].size()==2)return 0;
		for(int j:cycle[i]) {
			for(int k:cycle[i]) {
				if(j==k)continue;
				if(p[j][k]!=2)return 0;
			}
		}
		for(int j = 0;j<(int)cycle[i].size()-1;j++) {
			ans[cycle[i][j]][cycle[i][j+1]]=1;
			ans[cycle[i][j+1]][cycle[i][j]]=1;
		}
		ans[cycle[i][0]][cycle[i].back()]=1;
		ans[cycle[i].back()][cycle[i][0]]=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