Submission #304992

#	Time	Username	Problem	Language	Result	Execution time	Memory
304992		Wu_Ren	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	269 ms	22392 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int n,m,fa[1010],d[1010];
int find(int a){
	return fa[a]==a?a:fa[a]=find(fa[a]);
}
int merge(int u,int v){
	u=find(u),v=find(v);
	if(u==v) return false;
	fa[u]=v;return true;
}
struct node{
	int id,fa;
	bool operator <(const node &b)const{
		return fa<b.fa;
	}
}c[1010];
int construct(vector<vector<int> >p){
	n=p.size();
	vector<vector<int> >ans;
	for(int i=0;i<n;i++){
		vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for(int i=0;i<n;i++) fa[i]=i;
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){
		if(p[i][j]>=3) return false;
		if(p[i][j]==1) merge(i,j);
	}
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j]!=p[find(i)][find(j)]) return false;
	for(int i=0;i<n;i++) fa[i]=i;
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){
		if(p[i][j]==1){
			if(merge(i,j)) ans[i][j]=ans[j][i]=1;
		}
	}
	for(int i=0;i<n;i++) d[i]=find(i),fa[i]=i;
	sort(d,d+n);
	int sz=unique(d,d+n)-d;
	for(int i=0;i<sz;i++){
		for(int j=i+1;j<sz;j++){
			if(p[d[i]][d[j]]==2) merge(d[i],d[j]);
		}
	}
	for(int i=0;i<sz;i++){
		for(int j=i+1;j<sz;j++){
			if((p[d[i]][d[j]]==0&&find(d[i])==find(d[j]))||(p[d[i]][d[j]]==2&&find(d[i])!=find(d[j]))) return 0;
		}
	}
	for(int i=0;i<sz;i++) c[i].id=d[i],c[i].fa=find(d[i]);
	sort(c,c+sz);
	for(int i=0,lst=0;i<sz;i++){
		if(i&&c[i].fa==c[i-1].fa) ans[c[i].id][c[i-1].id]=ans[c[i-1].id][c[i].id]=1;
		if(i&&c[i].fa!=c[i-1].fa){
			if(lst!=i-1) ans[c[i-1].id][c[lst].id]=ans[c[lst].id][c[i-1].id]=1;
			if(lst==i-2) return false;
			lst=i;
		}
		if(i==sz-1){
			if(lst==i-1) return false;
			if(lst!=i) ans[c[i].id][c[lst].id]=ans[c[lst].id][c[i].id]=1;
		}
	}
	build(ans);
	return true;
}

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