Submission #716428

#	Time	Username	Problem	Language	Result	Execution time	Memory
716428		Baytoro	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	187 ms	24064 KiB

supertrees

#include "supertrees.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int> p,sz;
	void build(int n){
		p.resize(n);
		sz.resize(n);
		for(int i=0;i<n;i++){
			p[i]=i;
			sz[i]=1;
		}
	}
	int f(int x){
		if(p[x]==x) return x;
		return p[x]=f(p[x]);
	}
	void add_edge(int a, int b){
		a=f(a);b=f(b);
		if(a==b) return;
		if(sz[a]>sz[b]) swap(a,b);
		p[a]=b;
		sz[b]+=sz[a];
	}
};
int construct(vector<vector<int>> p) {
	int n = p.size();
	DSU trees,comp;
	trees.build(n);comp.build(n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==3) return 0;
			if(p[i][j]==1)
				trees.add_edge(i,j);
			if(p[i][j]>0)
				comp.add_edge(i,j);
		}
	}
	for(int i=0;i<n && 0;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==0 && comp.f(i)!=comp.f(j)) return 0;
			if(p[i][j]!=0 && comp.f(i)==comp.f(j)) return 0;
			if(p[i][j]==1 && trees.f(i)!=trees.f(j)) return 0;
			if(p[i][j]!=1 && trees.f(i)==trees.f(j)) return 0;
			if(p[i][j]==2 && comp.f(i)!=comp.f(j) && trees.f(i)==trees.f(j)) return 0;
			if(p[i][j]!=2 && comp.f(i)==comp.f(j) && trees.f(i)!=trees.f(j)) return 0;
		}
	}
	vector<int> used(n);
	vector<vector<int>> b(n,vector<int>(n,0));
	vector<vector<int>> v(n);
	for(int i=0;i<n;i++){
		if(!used[i]){
			used[i]=1;
			v[comp.f(i)].push_back(i);
			for(int j=0;j<n;j++){
				if(j!=i && trees.f(i)==trees.f(j)){
					b[i][j]=b[j][i]=1;
					used[j]=1;
				}
			}
		}
	}
	for(auto it: v){
		if(it.size()==2) return 0;
		if(it.size()>2){
			for(int i=0;i<(int)it.size();i++){
				b[it[i]][(it[(i+1)%(int)it.size()])]=b[(it[(i+1)%(int)it.size()])][it[i]]=1;
			}
		}
	}
	build(b);
	return 1;
}

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