oj.uz

Submission #118190

# Submission time Handle Problem Language Result Execution time Memory
118190 2019-06-18T10:31:56 Z Bruteforceman Izlet (COI19_izlet) C++11
100 / 100
 944 ms 51444 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;

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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 765 ms 51320 KB Output is correct
3 Correct 759 ms 50968 KB Output is correct
4 Correct 766 ms 50040 KB Output is correct
5 Correct 750 ms 48712 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 36192 KB Output is correct
2 Correct 750 ms 51320 KB Output is correct
3 Correct 888 ms 41208 KB Output is correct
4 Correct 944 ms 41208 KB Output is correct
5 Correct 741 ms 51064 KB Output is correct
6 Correct 782 ms 38136 KB Output is correct
7 Correct 576 ms 32248 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 765 ms 51320 KB Output is correct
3 Correct 759 ms 50968 KB Output is correct
4 Correct 766 ms 50040 KB Output is correct
5 Correct 750 ms 48712 KB Output is correct
6 Correct 749 ms 36192 KB Output is correct
7 Correct 750 ms 51320 KB Output is correct
8 Correct 888 ms 41208 KB Output is correct
9 Correct 944 ms 41208 KB Output is correct
10 Correct 741 ms 51064 KB Output is correct
11 Correct 782 ms 38136 KB Output is correct
12 Correct 576 ms 32248 KB Output is correct
13 Correct 827 ms 37688 KB Output is correct
14 Correct 835 ms 38456 KB Output is correct
15 Correct 777 ms 51444 KB Output is correct
16 Correct 823 ms 37816 KB Output is correct
17 Correct 833 ms 38296 KB Output is correct
18 Correct 727 ms 51192 KB Output is correct
19 Correct 791 ms 51148 KB Output is correct
20 Correct 816 ms 51192 KB Output is correct
21 Correct 752 ms 37624 KB Output is correct
22 Correct 789 ms 50936 KB Output is correct
23 Correct 801 ms 37624 KB Output is correct
24 Correct 878 ms 38336 KB Output is correct
25 Correct 771 ms 50960 KB Output is correct