oj.uz

Submission #313354

# Submission time Handle Problem Language Result Execution time Memory
313354 2020-10-15T20:58:21 Z luciocf Izlet (COI19_izlet) C++14
100 / 100
 1242 ms 74872 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];
int cc, tot;

int dfs(int u, int p, int root)
{
	if (cor[u])
	{
		++qtd[cor[u]];
		if (qtd[cor[u]] == 1) ++tot;
	}

	if (cor[u] && tot == a[root][u]) return cor[u];

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		int c = dfs(v, u, root);
		if (c) return c;
	}

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

	return 0;
}

int get_cor(int u)
{
	memset(qtd, 0, sizeof qtd); tot = 0;
	
	int c = dfs(u, 0, u);

	return (c ? c : ++cc);
}

void paint(int u, int p)
{
	cor[u] = get_cor(u);

	for (auto v: grafo[u])
		if (v != p)
			paint(v, u);
}
 
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);
 
	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);
			}
		}
	}
 
	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);
			}
		}
	}
 
	paint(1, 0);
 
	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:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |  scanf("%d", &s);
      |  ~~~~~^~~~~~~~~~
izlet.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
izlet.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |    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 918 ms 38264 KB Output is correct
3 Correct 961 ms 38136 KB Output is correct
4 Correct 927 ms 40952 KB Output is correct
5 Correct 926 ms 41464 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 36064 KB Output is correct
2 Correct 915 ms 53880 KB Output is correct
3 Correct 1208 ms 74076 KB Output is correct
4 Correct 1242 ms 74872 KB Output is correct
5 Correct 912 ms 53752 KB Output is correct
6 Correct 963 ms 60716 KB Output is correct
7 Correct 713 ms 49532 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 918 ms 38264 KB Output is correct
3 Correct 961 ms 38136 KB Output is correct
4 Correct 927 ms 40952 KB Output is correct
5 Correct 926 ms 41464 KB Output is correct
6 Correct 904 ms 36064 KB Output is correct
7 Correct 915 ms 53880 KB Output is correct
8 Correct 1208 ms 74076 KB Output is correct
9 Correct 1242 ms 74872 KB Output is correct
10 Correct 912 ms 53752 KB Output is correct
11 Correct 963 ms 60716 KB Output is correct
12 Correct 713 ms 49532 KB Output is correct
13 Correct 928 ms 54504 KB Output is correct
14 Correct 1152 ms 61488 KB Output is correct
15 Correct 908 ms 53624 KB Output is correct
16 Correct 1014 ms 58016 KB Output is correct
17 Correct 1024 ms 60024 KB Output is correct
18 Correct 903 ms 53744 KB Output is correct
19 Correct 956 ms 53624 KB Output is correct
20 Correct 934 ms 53644 KB Output is correct
21 Correct 943 ms 54520 KB Output is correct
22 Correct 972 ms 54008 KB Output is correct
23 Correct 944 ms 54488 KB Output is correct
24 Correct 1014 ms 60792 KB Output is correct
25 Correct 934 ms 53880 KB Output is correct