Submission #1034248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034248		Gray	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	150 ms	26196 KiB

supertrees

#include "supertrees.h"
#include <cassert>
#include <map>
#include <vector>
 
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
 
struct DSU{
	vector<int> p;
	int n, cnt;
	DSU(int N){
		n=N;
		cnt=n;
		p.resize(n, -1);
	}
	int get(int x){
		return p[x]==-1?x:p[x]=get(p[x]);
	}
	bool unite(int a, int b){
		a=get(a);
		b=get(b);
		if (a==b) return 0;
		cnt--;
		if (a<b) swap(a, b);
		p[a]=b;
		return 1;
	}
};
 
int construct(std::vector<std::vector<int>> p) {
	int n = (int)p.size();
	DSU tr(n), tr2(n);
	vector<vector<int>> A(n);
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (i!=j and p[i][j]){
				tr.unite(i, j);
				if (p[i][j]==1) tr2.unite(i, j);
			}
		}
	}
	map<int, vector<int>> ccs;
	for (int i=0; i<n; i++){
		// assert(tr.get(i)<tr.cnt);
		ccs[tr.get(i)].push_back(i);
	}
	vector<vector<int>> ans(n, vector<int>(n));
	vector<vector<int>> shadow(n, vector<int>(n));
	for (auto &[_, arr]:ccs){
		map<int, vector<int>> groups;
		for (auto ch:arr){
			groups[tr2.get(ch)].push_back(ch);
		}
		for (ll j=0; j<(int)(arr.size()); j++){
			for (ll k=j+1; k<(int)(arr.size()); k++){
				shadow[arr[j]][arr[k]]=shadow[arr[k]][arr[j]]=2;
			}
		}
		vector<int> circle;
		for (auto &[icc,mem]:groups){
			for (ll j=1; j<(int)mem.size(); j++){
				ans[mem[j]][mem[j-1]]=ans[mem[j-1]][mem[j]]=1;
			}
			for (ll j=0; j<(int)mem.size(); j++){
				for (ll k=j+1; k<(int)mem.size(); k++){
					shadow[mem[j]][mem[k]]=shadow[mem[k]][mem[j]]=1;
				}
			}
			circle.push_back(mem[0]);
		}
		if (circle.size()==1) continue;
		for (ll j=0; j<(int)circle.size(); j++){
			int nxt = (j+1)%(int)(circle.size());
			ans[circle[j]][circle[nxt]]=ans[circle[nxt]][circle[j]]=1;
		}
	}
	for (ll i=0; i<n; i++){
		for (ll j=0; j<n; j++){
			if ((i!=j and p[i][j]!=shadow[i][j]) or p[i][j]==3){
				return 0;
			}
		}
	}
	build(ans);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4