oj.uz

Submission #366313

# Submission time Handle Problem Language Result Execution time Memory
366313 2021-02-13T23:21:06 Z MetB Izlet (COI19_izlet) C++14
0 / 100
 1516 ms 53372 KB 
#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];
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;
}

int check_dfs(int x, int p, int root, int dist) {
	if (f[root][x] == dist) return cl[x];
	int ans = 0;
	for (auto to : g[x]) {
		if (cl[to] && to != p) {
			ans = max(ans, check_dfs(to, x, root, dist + 1));
		}
	}

	return ans;
}

int main() {
	cin >> n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		p[i] = i;
		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;

		cl[x] = check_dfs(x, -1, x, 0);
		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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1516 ms 53372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -