oj.uz

Submission #366675

# Submission time Handle Problem Language Result Execution time Memory
366675 2021-02-14T23:37:00 Z MetB Izlet (COI19_izlet) C++14
0 / 100
 1503 ms 36588 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]) {
		cl[root] = cl[x];
	}

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

	int ans;

	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';
		}
	}
}

Compilation message

izlet.cpp: In function 'void check_dfs(int, int, int)':
izlet.cpp:41:6: warning: unused variable 'ans' [-Wunused-variable]
   41 |  int ans;
      |      ^~~

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 1503 ms 36588 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 -