Submission #948011

#	Time	Username	Problem	Language	Result	Execution time	Memory
948011		4QT0R	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	193 ms	24404 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define loop(a,b,c) for(int a = b; a<(int)c; a++)

struct DSU{
	vi leader;
	vi siz;

	void init(int n){
		leader.resize(n+1);
		siz.resize(n+1);
		for (int i = 0; i<n; i++){
			leader[i]=i;
			siz[i]=1;
		}
	}
	
	int Find(int v){
		if (leader[v]==v)return v;
		leader[v]=Find(leader[v]);
		return leader[v];
	}

	bool same_set(int a, int b){
		return Find(a)==Find(b);
	}

	void Union(int a, int b){
		a=Find(a);
		b=Find(b);
		if (a==b)return;
		if (siz[a]<siz[b])swap(a,b);
		leader[b]=a;
		siz[a]+=siz[b];
	}
};

bool vis_branch[1502];
bool vis_comp[1502];
int nr_branch[1502];
int nr_comp[1502];

int construct(vvi p){
	int n=p.size();

	DSU compound,branch;
	compound.init(n);
	branch.init(n);
	vvi wyn;
	wyn.resize(n);
	loop(i,0,n)wyn[i].resize(n);
	loop(i,0,n){
		loop(j,0,n){
			if (p[i][j]){
				if (p[i][j]==3)return 0;
				compound.Union(i,j);
				if (p[i][j]==1)branch.Union(i,j);
			}
		}
	}
	loop(i,0,n){
		loop(j,i+1,n){
			if (p[i][j]==0 && compound.same_set(i,j))return 0;
			if (p[i][j]==2 && branch.same_set(i,j))return 0;
		}
	}
	vvi single;
	vvi cycle;
	int iter=0,iter2=0;
	loop(i,0,n){
		if (!vis_branch[branch.Find(i)]){
			if (!vis_comp[compound.Find(i)]){
				vis_comp[compound.Find(i)]=true;
				cycle.push_back({i});
				nr_comp[compound.Find(i)]=iter2++;
			}
			else cycle[nr_comp[compound.Find(i)]].push_back(i);
			vis_branch[branch.Find(i)]=true;
			single.push_back({i});
			nr_branch[branch.Find(i)]=iter++;
		}
		else single[nr_branch[branch.Find(i)]].push_back(i);
	}
	loop(i,0,iter){
		loop(j,1,single[i].size()){
			wyn[single[i][0]][single[i][j]]=wyn[single[i][j]][single[i][0]]=1;
		}
	}
	loop(i,0,iter2){
		if (cycle[i].size()==1)continue;
		else if (cycle[i].size()==2)return 0;
		wyn[cycle[i][0]][cycle[i].back()]=wyn[cycle[i].back()][cycle[i][0]]=1;
		loop(j,1,cycle[i].size()){
			wyn[cycle[i][j-1]][cycle[i][j]]=wyn[cycle[i][j]][cycle[i][j-1]]=1;
		}
	}
	build(wyn);
	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