Submission #822198

#	Time	Username	Problem	Language	Result	Execution time	Memory
822198		Username4132	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	229 ms	24120 KiB

supertrees

#include "supertrees.h"
#include<iostream>
#include <vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back

const int MAXN = 1010;
int n;
bool vi1[MAXN], vi2[MAXN], ad1[MAXN][MAXN], ad2[MAXN][MAXN];
vector<int> comp;

void dfs(int v, bool* vis, bool adj[][MAXN]){
	vis[v]=true;
	comp.PB(v);
	forn(i, n) if(!vis[i] && adj[v][i]) dfs(i, vis, adj);
}

bool check(vector<int>& com, bool adj[][MAXN]){
	bool ret = true;
	int sz = (int)com.size();
	forn(i, sz) forsn(j, i+1, sz) ret &= adj[com[i]][com[j]];
	return ret;
}



int construct(std::vector<std::vector<int>> p) {
	n = (int)p.size();
	std::vector<std::vector<int>> ans(n, vector<int>(n, 0));
	bool has3 = false;
	forn(i, n) forn(j, n) has3 |= (p[i][j] == 3);
	if(has3) return 0;
	forn(i, n) forn(j, n) ad1[i][j] = (p[i][j] > 0);
	forn(i, n) forn(j, n) ad2[i][j] = (p[i][j] == 1);
	forn(i, n) if(!vi1[i]){
		dfs(i, vi1, ad1);
		if(!check(comp, ad1)) return 0;
		vector<int> al, rep;
		swap(comp, al);
		for(int el:al) if(!vi2[el]){
			dfs(el, vi2, ad2);
			if(!check(comp, ad2)) return 0;
			forn(j, comp.size() - 1) ans[comp[j]][comp[j+1]]=ans[comp[j+1]][comp[j]]=1;
			rep.PB(comp.back());
			comp.clear();
		}
		if((int)rep.size() == 2) return 0;
		if((int)rep.size() > 2){
			forn(j, rep.size() - 1) ans[rep[j]][rep[j+1]]=ans[rep[j+1]][rep[j]]=1;
			ans[rep.front()][rep.back()]=ans[rep.back()][rep.front()]=1;
		}
	}
	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