Submission #1268003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268003		WH8	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	104 ms	22188 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<vector<int>> r;
int n;
vector<int> p(1005, -1);
int par(int x){
	if(p[x]==-1)return x;
	return p[x]=par(p[x]);
}
void merge(int a, int b){
	int x=par(a), y=par(b);
	if(x==y)return;
	p[x]=y;
}
vector<vector<int>> comps;
vector<vector<int>> ans;
bool comp(vector<int> v){
	//~ cout<<"COMPONENT : \n";
	//~ for(auto it: v){
		//~ cout<<it<<" ";
	//~ }
	//~ cout<<endl;
	
	int mx=0;
	for(auto node:v){
		for(int j=0;j<n;j++){
			mx=max(r[node][j], mx);
		}
	}
	if(mx==0)return 1;
	if(mx==1){
		for(int i=0;i<(int)v.size()-1;i++){
			ans[v[i]][v[i+1]]=1;
			ans[v[i+1]][v[i]]=1;
		}
		return 1;
	}
	//~ cout<<"HERE"<<endl;
	assert(mx==2);
	for(auto node:v){
		for(int j=0;j<n;j++){
			if(r[node][j] == 1) merge(node, j);
		}
	}
	for(auto node:v){
		for(int j=0;j<n;j++){
			if(r[node][j] == 2 and par(node)==par(j)) return 0;
		}
	}
	//~ return 1;
	vector<vector<int>> wings;
	vector<int> label(1005, -1);
	int t=0;
	for(auto node : v){
		if (label[par(node)] == -1){
			wings.pb(vector<int>{node});
			label[par(node)] = t++;
		}
		else wings[label[par(node)]].pb(node);
	}
	if(wings.size() <= 2)return 0;
	//~ cout<<"WINGS : \n";
	//~ for(auto & wing : wings){
		//~ for(auto & item : wing){
			//~ cout<<item<<" ";
		//~ }
		//~ cout<<endl;
	//~ }
	//~ cout<<endl;
	for(int i=0;i<(int)wings.size();i++){
		for(int j=0;j<(int)wings[i].size()-1;j++){
			ans[wings[i][j]][wings[i][j+1]]=1;
			ans[wings[i][j+1]][wings[i][j]]=1;
		}
		if(i < (int)wings.size()){
			ans[wings[i][0]][wings[(i+1)%(wings.size())][0]]=1;
			ans[wings[(i+1)%(wings.size())][0]][wings[i][0]]=1;
		}
	}
	return 1;	
}

int construct(vector<vector<int>> coc) {
	swap(r, coc);
	n = r.size();
	ans.resize(n);
	for(int i=0;i<n;i++){
		ans[i].resize(n);
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//~ cout<<r[i][j]<<" ";
			if(r[i][j]>0)merge(i,j);
			if(r[i][j]==3)return 0;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(r[i][j]==0 and par(i)==par(j)){
				return 0;
			}
		}
	}
	vector<int> label(1005, -1);
	int t=0;
	for(int i=0;i<n;i++){
		if (label[par(i)] == -1){
			comps.pb({i});
			label[par(i)] = t++;
		}
		else comps[label[par(i)]].pb(i);
	}
	for(int i=0;i<n;i++)p[i]=-1; // reset;
	for(int i=0;i<(int)comps.size();i++){
		if(!comps[i].empty()){
			//~ cout<<"COMP "<<i<<endl;
			int res=comp(comps[i]);
			if(!res) return 0;
		}
	}
	//~ for(int i=0;i<n;i++)ans[i][i]=1;
	//~ for(auto & row : ans){
		//~ for(auto & item : row){
			//~ cout<<item<<" ";
		//~ }
		//~ cout<<endl;
	//~ }
	build(ans);
	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