oj.uz

답안 #253560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253560 2020-07-28T09:52:18 Z erray Izlet (COI19_izlet) C++14
100 / 100
 1382 ms 61432 KB 
#include<bits/stdc++.h>
 
using namespace std;
	
class dsu {
	public:
	vector<int> par, ct;
	dsu(int sz) {
		ct.resize(sz, 1);
		par.resize(sz);
		iota(par.begin(), par.end(), 0);
	}
	int get_par(int nd) {
		return (par[nd] == nd ? nd : get_par(par[nd]));
	}
	bool Merge(int a, int b) {
		a = get_par(a), b = get_par(b);
		if (a == b) return false;
		if (ct[a] < ct[b]) swap(a, b);
		ct[a] += ct[b];
		par[b] = a;
		return true;
	}
}; 
int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int type, n;
	cin >> type >> n;
	vector<vector<int>> adj(n, vector<int>(n));
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> adj[i][j];
	dsu graph(n);
	vector<pair<int, int>> edges;
	vector<vector<int>> g(n);
	auto add_edge = [&](int val) {
		for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
			if (adj[i][j] == val && graph.Merge(i, j)) {
				edges.emplace_back(i, j);				
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	};
	add_edge(1); add_edge(2);
	dsu col(n);
	for (int i = 0; i < n; ++i) {
		for (auto ad : g[i]) {
			function<int(int, int)> dfs = [&](int nd, int par) {
				int res = -1;
				if (adj[nd][ad] == adj[nd][i]) {
					return nd;
				}	
				for (auto el : g[nd]) {
					if (el == par) continue;
					res = max(dfs(el, nd), res);
				}
				return res;
			};
			int source = dfs(ad, i);
			if (source != -1) {
				col.Merge(source, i);
			}
		}
	}
	for (int i = 0; i < n; ++i) cout << col.get_par(i) + 1 << ' ';
	for (auto el : edges) cout << '\n' << el.first + 1 << ' ' << el.second + 1;
}

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 931 ms 36732 KB Output is correct
3 Correct 872 ms 36856 KB Output is correct
4 Correct 757 ms 36744 KB Output is correct
5 Correct 771 ms 36684 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 633 ms 36856 KB Output is correct
2 Correct 771 ms 36856 KB Output is correct
3 Correct 938 ms 37992 KB Output is correct
4 Correct 980 ms 38008 KB Output is correct
5 Correct 609 ms 36856 KB Output is correct
6 Correct 701 ms 36944 KB Output is correct
7 Correct 521 ms 26652 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 931 ms 36732 KB Output is correct
3 Correct 872 ms 36856 KB Output is correct
4 Correct 757 ms 36744 KB Output is correct
5 Correct 771 ms 36684 KB Output is correct
6 Correct 633 ms 36856 KB Output is correct
7 Correct 771 ms 36856 KB Output is correct
8 Correct 938 ms 37992 KB Output is correct
9 Correct 980 ms 38008 KB Output is correct
10 Correct 609 ms 36856 KB Output is correct
11 Correct 701 ms 36944 KB Output is correct
12 Correct 521 ms 26652 KB Output is correct
13 Correct 822 ms 37112 KB Output is correct
14 Correct 1382 ms 61432 KB Output is correct
15 Correct 632 ms 53624 KB Output is correct
16 Correct 753 ms 58132 KB Output is correct
17 Correct 735 ms 59960 KB Output is correct
18 Correct 663 ms 53624 KB Output is correct
19 Correct 916 ms 53544 KB Output is correct
20 Correct 763 ms 53584 KB Output is correct
21 Correct 928 ms 54264 KB Output is correct
22 Correct 841 ms 53796 KB Output is correct
23 Correct 955 ms 54268 KB Output is correct
24 Correct 794 ms 60664 KB Output is correct
25 Correct 698 ms 53752 KB Output is correct