Submission #360213

#	Time	Username	Problem	Language	Result	Execution time	Memory
360213		NachoLibre	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1228 ms	1976148 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "supertrees.h"
#else
void build(vector<vector<int>> b) {}
#endif

const int N = 1003;
int dop[N];
int P(int x) {
	return (dop[x] ? dop[x] = P(dop[x]) : x);
}
void U(int x, int y) {
	dop[P(x)] = (P(x) ^ P(y) ? P(y) : -1);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> b(n);
	for(int i = 0; i < n; ++i) {
		dop[i] = -1;
		b[i].resize(i);
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(p[i][j] == 3) return 0;
			if(p[i][j] == 1) U(i, j);
		}
	}
	vector<int> dopn(n, -1), ep(n);
	vector<vector<int>> v;
	for(int i = 0; i < n; ++i) {
		ep[i] = P(i);
		if(dopn[P(i)] == -1) {
			dopn[P(i)] = v.size();
			v.push_back({});
		}
		v[dopn[P(i)]].push_back(i);
		if(p[v[dopn[P(i)]][0]] != p[i]) return 0;
	}
	int m = v.size();
	for(int i = 0; i < m; ++i) {
		for(int j = 1; j < (int)v[i].size(); ++j) {
			b[v[i][j - 1]][v[i][j]] = 1;
			b[v[i][j]][v[i][j - 1]] = 1;
		}
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < m; ++i) {
		dop[i] = -1;
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(v[i][j] == 2) U(dopn[ep[i]], dopn[ep[j]]);
		}
	}
	vector<vector<int>> q = p;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(q[i][j] == 1) q[i][j] = 2;
		}
	}
	vector<int> dopm(n, -1);
	vector<vector<int>> u;
	for(int i = 0; i < m; ++i) {
		if(dopm[P(i)] == -1) {
			dopm[P(i)] = u.size();
			u.push_back({});
		}
		u[dopm[P(i)]].push_back(i);
		if(q[v[u[dopm[P(i)]][0]][0]] != q[v[i][0]]) return 0;
	}
	int k = u.size();
	for(int i = 0; i < k; ++i) {
		if(u[i].size() == 1) continue;
		if(u[i].size() == 2) return 0;
		for(int j = 1; j < (int)u[i].size(); ++j) {
			int x = u[i][j], y = u[i][j - 1];
			b[v[x][0]][v[y][0]] = 1;
			b[v[y][0]][v[x][0]] = 1;
		}
		int x = u[i][0], y = u[i][(int)u[i].size() - 1];
		b[v[x][0]][v[y][0]] = 1;
		b[v[y][0]][v[x][0]] = 1;
	}
	build(b);
	return 1;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

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