oj.uz

Submission #218911

# Submission time Handle Problem Language Result Execution time Memory
218911 2020-04-03T05:55:13 Z dolphingarlic Izlet (COI19_izlet) C++14
100 / 100
 743 ms 71416 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int k, n, a[3001][3001], apsp[3001][3001];
int colour[3001], c = 1, e = 1;
bool visited[3001];
vector<int> in_tree;
pair<int, int> edges[3001];

void dfs(int node = 1) {
	visited[node] = true;
	in_tree.push_back(node);

	FOR(i, 1, n + 1) if (!visited[i] && a[node][i] == 1) {
		visited[i] = true;
		colour[i] = colour[node];
		for (int j : in_tree) apsp[i][j] = apsp[j][i] = apsp[node][j] + 1;
		edges[e++] = {node, i};
	}

	FOR(i, 1, n + 1) if (!visited[i] && a[node][i] == 2) {
		int mn_same = 0;
		for (int j : in_tree) {
			apsp[i][j] = apsp[j][i] = apsp[node][j] + 1;
			if (a[i][j] == a[node][j] && (!mn_same || apsp[i][j] < apsp[i][mn_same])) mn_same = j;
		}
		if (mn_same) colour[i] = colour[mn_same];
		else colour[i] = ++c;
		edges[e++] = {node, i};
		dfs(i);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> k >> n;
	FOR(i, 1, n + 1) FOR(j, 1, n + 1) cin >> a[i][j];
	colour[1] = 1;
	dfs();

	FOR(i, 1, n + 1) cout << colour[i] << ' ';
	cout << '\n';
	FOR(i, 1, n) cout << edges[i].first << ' ' << edges[i].second << '\n';
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 592 ms 71288 KB Output is correct
3 Correct 579 ms 71416 KB Output is correct
4 Correct 589 ms 58644 KB Output is correct
5 Correct 521 ms 65016 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 69652 KB Output is correct
2 Correct 539 ms 67448 KB Output is correct
3 Correct 711 ms 71288 KB Output is correct
4 Correct 743 ms 71288 KB Output is correct
5 Correct 594 ms 64504 KB Output is correct
6 Correct 548 ms 67576 KB Output is correct
7 Correct 420 ms 56440 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 592 ms 71288 KB Output is correct
3 Correct 579 ms 71416 KB Output is correct
4 Correct 589 ms 58644 KB Output is correct
5 Correct 521 ms 65016 KB Output is correct
6 Correct 561 ms 69652 KB Output is correct
7 Correct 539 ms 67448 KB Output is correct
8 Correct 711 ms 71288 KB Output is correct
9 Correct 743 ms 71288 KB Output is correct
10 Correct 594 ms 64504 KB Output is correct
11 Correct 548 ms 67576 KB Output is correct
12 Correct 420 ms 56440 KB Output is correct
13 Correct 649 ms 71036 KB Output is correct
14 Correct 738 ms 71084 KB Output is correct
15 Correct 525 ms 69896 KB Output is correct
16 Correct 575 ms 70008 KB Output is correct
17 Correct 586 ms 64504 KB Output is correct
18 Correct 665 ms 70904 KB Output is correct
19 Correct 556 ms 65016 KB Output is correct
20 Correct 584 ms 69752 KB Output is correct
21 Correct 558 ms 66040 KB Output is correct
22 Correct 600 ms 70520 KB Output is correct
23 Correct 602 ms 70392 KB Output is correct
24 Correct 656 ms 70776 KB Output is correct
25 Correct 534 ms 70520 KB Output is correct