Submission #118190

#	Time	Username	Problem	Language	Result	Execution time	Memory
118190		Bruteforceman	Izlet (COI19_izlet)	C++11	100 / 100	944 ms	51444 KiB

izlet

#include "bits/stdc++.h"
using namespace std;
int n;
int a[3005][3005];
int par[3005];
vector <int> g[3005];
vector <pair <int, int>> edg;

int root(int x) {
	if(par[x] == x) return par[x];
	return par[x] = root(par[x]);
}
int join(int x, int y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		par[x] = y;
	}
}

void add_edge(int x, int y) {	
	g[x].push_back(y);
	g[y].push_back(x);
	edg.emplace_back(x, y);
	join(x, y);
	// cout << x << ' ' << y << endl;
}

int occ[3005];
int col[3005];
bool vis[3005];
int piv;
int cur;

void getColor(int x, int par) {
	if(occ[col[x]] == 0) {
		if(a[piv][x] == a[piv][par]) {
			col[piv] = col[x];
		}
	}
	if(par != 0) ++occ[col[x]];
	for(auto i : g[x]) {
		if(vis[i] && i != par) {
			getColor(i, x);
		}
	}
	if(par != 0) --occ[col[x]];
}
void dfs(int x, int par) {
	vis[x] = true;
	piv = x;
	getColor(x, 0);

	if(col[x] == 0) {
		col[x] = ++cur;
	}
	for(int i : g[x]) {
		if(i != par) {
			dfs(i, x);
		}
	}
}

int main(int argc, char const *argv[])
{
	int subtask;
	scanf("%d", &subtask);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for(int i = 1; i <= n; i++) {
		par[i] = i;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(a[i][j] == 1) {
				join(i, j);
			}
		}
	}
	set <int> s;
	for(int i = 1; i <= n; i++) s.insert(root(i));
	for(int i = 1; i <= n; i++) {
		if(i != root(i)) {
			add_edge(i, root(i));
		}
	}
	vector <int> node (s.begin(), s.end());
	for(int i = 0; i < node.size(); i++) {
		for(int j = i + 1; j < node.size(); j++) {
			if(a[node[i]][node[j]] == 2) {
				if(root(node[i]) != root(node[j])) {
					add_edge(node[i], node[j]);
				}
			}
		}
	}

	occ[0] = 1;
	dfs(1, 0);

	for(int i = 1; i <= n; i++) printf("%d ", col[i]);
	printf("\n");
	for(auto e : edg) {
		printf("%d %d\n", e.first, e.second);
	}
	return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int join(int, int)':
izlet.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
izlet.cpp: In function 'int main(int, const char**)':
izlet.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < node.size(); i++) {
                 ~~^~~~~~~~~~~~~
izlet.cpp:93:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < node.size(); j++) {
                      ~~^~~~~~~~~~~~~
izlet.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &subtask);
  ~~~~~^~~~~~~~~~~~~~~~
izlet.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
izlet.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57