oj.uz

Submission #312670

# Submission time Handle Problem Language Result Execution time Memory
312670 2020-10-14T01:21:40 Z luciocf Izlet (COI19_izlet) C++14
0 / 100
 1313 ms 36344 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, cores;

int qtd[maxn], tot;

void dfs(int u, int p, int root)
{
	++qtd[cores.Find(u)];

	if (qtd[cores.Find(u)] == 1)
	{
		++tot;

		if (tot > a[root][u])
		{
			--qtd[cores.Find(u)];

			cores.Join(root, u);

			++qtd[cores.Find(u)], --tot;
		}
	}

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

	--qtd[cores.Find(u)];
	if (qtd[cores.Find(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);
	cores.init(n);
	
	for (int i = 1; i <= n; i++)
	{
		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);

				cores.Join(i, j);
			}
		}
	}

	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++)
		dfs(i, 0, i);

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

	for (int i = 1; i <= n; i++)
		printf("%d ", cor[cores.Find(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:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d", &s);
      |  ~~~~~^~~~~~~~~~
izlet.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
izlet.cpp:81:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1279 ms 36216 KB Output is correct
3 Correct 1277 ms 36120 KB Output is correct
4 Incorrect 1313 ms 35996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1257 ms 36344 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 1279 ms 36216 KB Output is correct
3 Correct 1277 ms 36120 KB Output is correct
4 Incorrect 1313 ms 35996 KB Output isn't correct
5 Halted 0 ms 0 KB -