Submission #300676

#	Time	Username	Problem	Language	Result	Execution time	Memory
300676		errorgorn	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	293 ms	26232 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

int n;
vector<vector<int> > arr;

bool vis[1005];
bool vis2[1005];
int comp[1005];
int subcomp[1005];

vector<vector<int> > ans;

int construct(std::vector<std::vector<int>> p) {
	n=p.size();
	arr=p;
	
	rep(x,0,n){
		rep(y,0,n) if (arr[x][y]==3) return 0;
	}
	
	rep(x,0,n){
		ans.push_back(vector<int>());
		rep(y,0,n) ans[x].push_back(0);
	}
	
	int idx=0;
	int idx2=0;
	rep(x,0,n) if (!vis[x]){
		vector<int> nodes;
		rep(y,0,n) if (arr[x][y] && !vis[y]){
			comp[y]=idx;
			vis[y]=true;
			nodes.push_back(y);
		}
		
		vector<vector<int> > comps;
		rep(y,0,sz(nodes)) if (!vis2[nodes[y]]){
			comps.push_back(vector<int>());
			
			rep(z,0,sz(nodes)) if (arr[nodes[y]][nodes[z]]==1 && !vis2[nodes[z]]){
				subcomp[nodes[z]]=idx2;
				vis2[nodes[z]]=true;
				comps.back().push_back(nodes[z]);
			}
			idx2++;
		}
		
		/*
		for (auto &it:comps){
			for (auto &iter:it) cout<<iter<<" "; cout<<endl;
		}
		*/
		
		for (auto &it:comps){
			rep(x,1,sz(it)) ans[it[0]][it[x]]=ans[it[x]][it[0]]=1;
		}
		
		if (sz(comps)==2) return 0;
		
		if (sz(comps)>1) rep(x,0,sz(comps)){
			ans[comps[x][0]][comps[(x+1)%sz(comps)][0]]=ans[comps[(x+1)%sz(comps)][0]][comps[x][0]]=1;
		}
		
		idx++;
	}
	
	//rep(x,0,n) cout<<comp[x]<<" "<<subcomp[x]<<endl;
	
	rep(x,0,n) rep(y,0,n){
		if (arr[x][y]==0){
			if (comp[x]==comp[y]) return 0;
		}
		else if (arr[x][y]==1){
			if (comp[x]!=comp[y] || subcomp[x]!=subcomp[y]) return 0;
		}
		else{
			if (comp[x]!=comp[y] || subcomp[x]==subcomp[y]) return 0;
		}
	}
	
	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