Submission #838332

#	Time	Username	Problem	Language	Result	Execution time	Memory
838332		ma_moutahid	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	188 ms	24064 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vii vector<vi>
vi d;
vi h;

int parent(int x){
	if(d[x]==x)return x;
	return d[x]=parent(d[x]);
}

void connect(int a, int b){
	a=parent(a);
	b=parent(b);
	if(a==b)return;

	if(h[a]<h[b])swap(a,b);
	d[b]=a;
	if(h[a]==h[b])h[a]++;
}



int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vii answer(n,vi(n));
	d.resize(n);h.resize(n,1);for(int i=0;i<n;i++)d[i]=i;
	for (int i = 0; i < n; i++) {
		for(int j=i+1;j<n;j++)if(p[i][j])connect(i,j);
	}
	vi bp(n,-1);
	vector<set<int>>bs;
	for(int i=0;i<n;i++){
		int pr=parent(i);
		if(h[pr]<=1)continue;
		if(bp[pr]==-1 ){
			bp[pr]=bs.size();
			bs.resize(bs.size()+1);
			
		}
		bs[bp[pr]].insert(i);
	}

	for( auto &s:bs){
		vector<set<int>>sets;
		vi pr(n,-1);
		for(auto itr1=s.begin();itr1!=s.end();itr1++){
			int a=*itr1;
			if(pr[a]==-1){
				pr[a]=sets.size();
				sets.resize(sets.size()+1);
				sets[pr[a]].insert(a);
			}
			for( auto itr2=itr1;itr2!=s.end();itr2++){
				int b=*itr2;
				if(p[a][b]==0)return 0;
				if(p[a][b]==1){
					pr[b]=pr[a];
					sets[pr[a]].insert(b);
					
				}
			}
		}
		vi v;
		for( auto &st:sets){
			v.push_back(*st.begin());
			for(auto itr=st.begin();next(itr)!=st.end();itr++){
				answer[(*itr)][(*next(itr))]=1;
				answer[*next(itr)][*itr]=1;
				for(auto itr2=next(itr);itr2!=st.end();itr2++){
					if(p[*itr][*itr2]>1)return 0;
				}
			}
		}
		int sz=v.size();
	
		if(sz<=1)continue;
		if(sz==2)return 0;
		int num=p[v[0]][v[sz-1]];
		answer[v[0]][v[sz-1]]=1;
		answer[v[sz-1]][v[0]]=1;
		for(int i=0;i<sz-1;i++){
			if(p[i][i+1]!=num)return 0;
			answer[i][i+1]=1;
			answer[i+1][i]=1;
		}
		if(num ==3 ){
			answer[0][2]=1;
			answer[2][0]=1;
		}
		
	}



	build(answer);
	return 1;
}

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