Submission #1200844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200844		Kerim	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	125 ms	26128 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
// #include "grader.cpp"
using namespace std;
 
int construct(vector<vector<int>> p) {
	int n = (int)p.size();
 
	vector<int> E[n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			assert(p[i][j] == p[j][i]);
 
			if (i == j) assert(p[i][j] == 1);
			else assert(!p[i][j] || p[i][j] == 2);
 
			if (p[i][j] == 2) E[i].push_back(j);
		}
	}
 
	vector<bool> vis(n);
	vector<vector<int>> ans(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
 
		int pre = i;
		queue<int> q;
		vector<int> v;
		q.push(i); vis[i] = true;
		while (!q.empty()) {
			int x = q.front(); q.pop();
 
			v.push_back(x);
 
			for (auto j : E[x]) {
				if (!vis[j]) {
					q.push(j);
					vis[j] = true;
					ans[pre][j] = ans[j][pre] = 1; pre = j;
				}
			}
		}
 
		// assert((int)v.size() != 1);
		if ((int)v.size() == 1){
		    assert(E[i].empty());
		    continue;
		}
 
		if ((int)v.size() == 2) return 0;
 
		for (auto j : v) {
			for (auto k : v)
				if (!p[j][k]) return 0;
		}
 
		ans[i][pre] = ans[pre][i] = 1;
	}
 
	build(ans);
 
	return 1;
}

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