oj.uz

Submission #312662

# Submission time Handle Problem Language Result Execution time Memory
312662 2020-10-14T01:00:02 Z luciocf Izlet (COI19_izlet) C++14
18 / 100
 1075 ms 36216 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 3e3+10;

int a[maxn][maxn];

int cor[maxn];
vector<pii> edge;

vector<int> grafo[maxn];

struct DSU
{
	int pai[maxn], peso[maxn];

	void init(int n)
	{
		for (int i = 1; i <= n; i++)
			pai[i] = i, peso[i] = 1;
	}

	int Find(int x)
	{
		if (pai[x] == x) return x;
		return pai[x] = Find(pai[x]);
	}

	void Join(int x, int y)
	{
		x = Find(x), y = Find(y);
		if (x == y) return;

		if (peso[x] < peso[y]) swap(x, y);

		pai[y] = x, peso[x] += peso[y];
	}
} dsu;

int qtd[maxn], tot;

void dfs(int u, int p, int root)
{
	if (!qtd[cor[u]]) ++tot;
	++qtd[cor[u]];

	if (a[root][u] < tot)
	{
		--qtd[cor[u]], --tot;
		cor[u] = cor[root];
		++qtd[cor[u]];
	}

	for (auto v: grafo[u])
		if (v != p)
			dfs(v, u, root);

	--qtd[cor[u]];
	if (qtd[cor[u]] == 0) --tot;
}

int main(void)
{
	int s;
	scanf("%d", &s);

	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);

	dsu.init(n);

	int cc = 0;

	for (int i = 1; i <= n; i++)
	{
		if (cor[i] == 0) cor[i] = ++cc;

		for (int j = i+1; j <= n; j++)
		{
			if (a[i][j] == 1 && dsu.Find(i) != dsu.Find(j))
			{
				edge.push_back({i, j});
				dsu.Join(i, j);

				grafo[i].push_back(j);
				grafo[j].push_back(i);

				cor[j] = cor[i];
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = i+1; j <= n; j++)
		{
			if (a[i][j] == 2 && dsu.Find(i) != dsu.Find(j))
			{
				edge.push_back({i, j});
				dsu.Join(i, j);

				grafo[i].push_back(j);
				grafo[j].push_back(i);
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= cc; j++)
			assert(qtd[j] == 0);
		assert(tot == 0);

		dfs(i, 0, i);
	}

	for (int i = 1; i <= n; i++)
		printf("%d ", cor[i]);
	printf("\n");
	for (int i = 1; i < n; i++)
		printf("%d %d\n", edge[i-1].first, edge[i-1].second);
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%d", &s);
      |  ~~~~~^~~~~~~~~~
izlet.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
izlet.cpp:75:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1059 ms 35976 KB Output is correct
3 Correct 1024 ms 36088 KB Output is correct
4 Correct 1075 ms 36088 KB Output is correct
5 Correct 1032 ms 35960 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1059 ms 35976 KB Output is correct
3 Correct 1024 ms 36088 KB Output is correct
4 Correct 1075 ms 36088 KB Output is correct
5 Correct 1032 ms 35960 KB Output is correct
6 Incorrect 1058 ms 36216 KB Output isn't correct
7 Halted 0 ms 0 KB -