Submission #234570

#	Time	Username	Problem	Language	Result	Execution time	Memory
234570		pedy4000	Izlet (COI19_izlet)	C++14	100 / 100	809 ms	50232 KiB

izlet

#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;

typedef pair <int, int> pii;

const int N = 3e3 + 9;
int n, ind;
vector <pii> ans;
int par[N];
bool del[N];
int col[N];
int dis[N][N];
vector <int> G[N];
int cnt;
int mark[N];

int root (int v) {
	return par[v] == v? v: par[v] = root(par[v]);
}

void dfs(int v, int p, int u) {
	cnt += !mark[col[v]];
	mark[col[v]]++;
	if (dis[v][u] < cnt)
		assert(false);
	if (dis[v][u] > cnt + 1)
		assert(false);
	if (dis[v][u] == cnt) {
		col[u] = min(col[u], col[v]);
		mark[col[v]]--;
		cnt -= !mark[col[v]];
		return ;
	}
	for (int k: G[v])
		if (k != p && col[k] != -1)
			dfs(k, v, u);

	mark[col[v]]--;
	cnt -= !mark[col[v]];
}

void calc(int v, int p = -1) {
	col[v] = ind;
	if (p != -1)
		dfs(p, v, v);

	ind += col[v] == ind;

	for (int u: G[v])
		if (u != p)
			calc(u, v);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> dis[i][j];

	for (int i = 0; i < n; i++)
		par[i] = i, col[i] = -1;

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (dis[i][j] == 1 && root(i) != root(j)) {
				ans.push_back({root(i), root(j)});
				del[root(j)] = true;
				par[root(j)] = root(i);
			}

	for (int i = 0; i < n; i++)
		if (del[i] == false)
			for (int j = i + 1; j < n; j++)
				if (del[j] == false && root(i) != root(j))
					if (dis[i][j] == 2) {
						ans.push_back({i, j});
						G[i].push_back(j);
						G[j].push_back(i);
						par[root(j)] = root(i);
					}

	calc(0);

	for (int i = 0; i < n; i++)
		if (col[i] == -1)
			col[i] = col[par[i]];

	for (int i = 0; i < n; i++)
		cout << col[i] + 1 << " ";
	cout << "\n";

	for (pii e: ans)
		cout << e.first + 1 << " " << e.second + 1 << "\n";
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57