Submission #366038

#	Time	Username	Problem	Language	Result	Execution time	Memory
366038		mjhmjh1104	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	280 ms	24428 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;

int uf[1006];

int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}

void _merge(int x, int y) {
    x = _find(x), y = _find(y);
    if (x != y) uf[x] = y;
}

vector<int> v[1006], u[1006];
vector<vector<int>> adj;

int construct(vector<vector<int>> p) {
	int n = p.size();
	adj.resize(n);
	for (int i = 0; i < n; i++) adj[i].resize(n, 0);
	for (int i = 0; i < n; i++) uf[i] = -1;
	for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (p[i][j]) _merge(i, j);
	for (int i = 0; i < n; i++) v[_find(i)].push_back(i);
	for (int t = 0; t < n; t++) for (int i = 0; i < (int)v[t].size(); i++) for (int j = 0; j < i; j++) if (p[v[t][i]][v[t][j]] == 0 || p[v[t][i]][v[t][j]] == 3) return 0;
	for (int t = 0; t < n; t++) if (!v[t].empty()) {
        for (int i = 0; i < n; i++) uf[i] = -1, u[i].clear();
        for (int i = 0; i < (int)v[t].size(); i++) for (int j = 0; j < i; j++) if (p[v[t][i]][v[t][j]] == 1) _merge(v[t][i], v[t][j]);
        for (int i = 0; i < (int)v[t].size(); i++) for (int j = 0; j < i; j++) if (_find(v[t][i]) == _find(v[t][j]) && p[v[t][i]][v[t][j]] == 2) return 0;
        for (int i = 0; i < (int)v[t].size(); i++) u[_find(v[t][i])].push_back(v[t][i]);
        vector<int> cycle;
        for (int i = 0; i < n; i++) if (!u[i].empty()) {
            cycle.push_back(u[i][0]);
            for (int j = 1; j < (int)u[i].size(); j++) adj[u[i][j - 1]][u[i][j]] = adj[u[i][j]][u[i][j - 1]] = 1;
        }
        for (int i = 1; i < (int)cycle.size(); i++) adj[cycle[i - 1]][cycle[i]] = adj[cycle[i]][cycle[i - 1]] = 1;
        if ((int)cycle.size() > 2) adj[cycle.back()][cycle[0]] = adj[cycle[0]][cycle.back()] = 1;
        else if ((int)cycle.size() == 2) return 0;
	}
	build(adj);
	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