Submission #311958

#	Time	Username	Problem	Language	Result	Execution time	Memory
311958		MrGary	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	291 ms	22520 KiB

supertrees

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
#include "supertrees.h"
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=1001;
struct my_dsu{
	vector<int> vec[MAXN];
	int fa[MAXN];
	int root(int u){
		return fa[u]=(fa[u]==u? u:root(fa[u]));
	}
	void merge(int u,int v){
		u=root(u);
		v=root(v);
		if(u==v) return;
		if(vec[u].size()>vec[v].size()) swap(u,v);
		for(auto it:vec[u])
			vec[v].PB(it);
		fa[u]=v;
		vec[u].clear();
	}
}dsu,dsu2;
bool three[MAXN];
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	rep(i,n)
		dsu.fa[i]=i,dsu.vec[i].PB(i),dsu2.fa[i]=i,dsu2.vec[i].PB(i);
	vector<vector<int> >  ans=vector<vector<int> > (n,vector<int> (n,0));
	rep(i,n)
		rep(j,n){
			if(p[i][j]==1){
				dsu.merge(i,j);
			}	
		}
	rep(i,n)
		rep(j,n)
			if(dsu.root(i)==dsu.root(j)){
				if(p[i][j]!=1) return 0;
			}
	rep(i,n)
		if(dsu.root(i)==i)
		{
			int las=-1;
			for(auto it:dsu.vec[i])
			{
				if(las!=-1){
					ans[las][it]=ans[it][las]=1;
				}
				las=it;
			}	
				 
		}
//	rep(i,n)
//		if(dsu.root(i)==i){
//			for(auto it:dsu.vec[i]) cout<<it<<' ';
//			cout<<endl;
//		}
	rep(i,n)
		rep(j,n)
			if(p[i][j]>1){
//				cout<<dsu.root(i)<<'_'<<dsu.root(j)<<endl;
				dsu2.merge(dsu.root(i),dsu.root(j));
			}
	rep(i,n)
		rep(j,n)
			if(dsu.root(i)!=dsu.root(j))
			if(dsu2.root(dsu.root(i))==dsu2.root(dsu.root(j))){
				if(p[i][j]<=1){
//					cout<<'!'<<' '<<i<<" "<<j<<endl;
					return false;
				}
			}
	rep(i,n)
		if(dsu2.root(i)==i){
			if(dsu2.vec[i].size()==1) continue;
			if(dsu2.vec[i].size()==2) return 0;
			int las=dsu2.vec[i].back();
			for(auto it:dsu2.vec[i]){
				ans[it][las]=ans[las][it]=1;
				las=it;
			}	
		}
//		cout<<"TONOW\n";
	rep(i,n)
		rep(j,n)
			if(p[i][j]==3){
				three[dsu2.root(dsu.root(i))]=1;
			}
	rep(i,n)
		if(three[i]){
			if(dsu2.vec[i].size()<=3) return 0;
			ans[dsu2.vec[i][0]][dsu2.vec[i][2]]=ans[dsu2.vec[i][2]][dsu2.vec[i][0]]=1;
		}
	rep(i,n)
		rep(j,n)
			if(dsu2.root(dsu.root(i))==dsu2.root(dsu.root(j))){
				if(three[dsu2.root(dsu.root(i))]){
					if(p[i][j]!=3) return false;
				}
			}
//	for(auto it:ans){
//		for(auto itt:it){
//			cout<<itt<<' ';
//		}
//		cout<<endl;
//	}
	build(ans);
	return 1;
}
//int main(){
//	fastio;
//	cout<<construct({{1,3},{3,1}});
//	return 0;
//}

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