oj.uz

Submission #366676

# Submission time Handle Problem Language Result Execution time Memory
366676 2021-02-14T23:38:25 Z MetB Izlet (COI19_izlet) C++14
18 / 100
 2000 ms 72556 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], 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() {
	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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1546 ms 53484 KB Output is correct
3 Correct 1564 ms 53792 KB Output is correct
4 Correct 1593 ms 53544 KB Output is correct
5 Correct 1556 ms 53304 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1500 ms 36004 KB Output is correct
2 Correct 1568 ms 53552 KB Output is correct
3 Execution timed out 2099 ms 72556 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1546 ms 53484 KB Output is correct
3 Correct 1564 ms 53792 KB Output is correct
4 Correct 1593 ms 53544 KB Output is correct
5 Correct 1556 ms 53304 KB Output is correct
6 Correct 1500 ms 36004 KB Output is correct
7 Correct 1568 ms 53552 KB Output is correct
8 Execution timed out 2099 ms 72556 KB Time limit exceeded
9 Halted 0 ms 0 KB -