oj.uz

Submission #118168

# Submission time Handle Problem Language Result Execution time Memory
118168 2019-06-18T09:43:15 Z Bruteforceman Izlet (COI19_izlet) C++11
0 / 100
 1191 ms 524288 KB 
#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;

void add_edge(int x, int y) {
	g[x].push_back(y);
	g[y].push_back(x);
	edg.emplace_back(x, y);
}

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

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];
		}
	}
	++occ[col[x]];
	for(auto i : g[x]) {
		if(vis[i] && i != par) {
			getColor(i, x);
		}
	}
	--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));

	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) {
				add_edge(node[i], node[j]);
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(i != root(i)) {
			add_edge(i, root(i));
		}
	}
	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

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

# Verdict Execution time Memory Grader output
1 Runtime error 487 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1191 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 487 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -