Submission #366677

#	Time	Username	Problem	Language	Result	Execution time	Memory
366677		MetB	Izlet (COI19_izlet)	C++14	100 / 100	782 ms	74604 KiB

izlet

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const ll N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const ll maxk = 1e6;

int f[3000][3000], n, cl[3000], p[3000], sz[3000], cnt[3000];
vector<int> g[3000];

int find(int x) {
	if (x == p[x]) return x;
	return p[x] = find(p[x]);
}

void unite(int a, int b) {
	if (find(a) == find(b)) return;
	g[a].push_back(b), g[b].push_back(a);

	a = find(a), b = find(b);
	if(sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	p[b] = a;
}

void check_dfs(int x, int p, int root) {
	if (p != -1 && f[root][x] == f[root][p] && !cnt[cl[x]]) {
		cl[root] = cl[x];
	}

	if (p != -1) ++cnt[cl[x]];

	for (auto to : g[x]) {
		if (cl[to] && to != p) {
			check_dfs(to, x, root);
		}
	}

	if (p != -1) --cnt[cl[x]];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		p[i] = i, sz[i] = 1;
		for (int j = 0; j < n; j++)
			cin >> f[i][j];
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (f[i][j] == 1) {
				unite(i, j);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (f[i][j] == 2) {
				unite(i, j);
			}
		}
	}

	queue<int> q;
	q.push(0);

	int ptr = 0;

	while(!q.empty()) {
		int x = q.front();
		q.pop();
		if (cl[x]) continue;

		check_dfs(x, -1, x);
		if (!cl[x]) cl[x] = ++ptr;

		for (auto to : g[x]) {
			if (!cl[to]) q.push(to);
		}
	}

	for (int i = 0; i < n; i++) {
		cout << cl[i] << ' ';
	}
	cout << endl;

	for (int i = 0; i < n; i++) {
		for (auto to : g[i]) {
			if (to < i) continue;
			cout << i + 1 << ' ' << to + 1 << '\n';
		}
	}
}

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