oj.uz

답안 #310820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310820 2020-10-08T05:22:43 Z ttnhuy313 Izlet (COI19_izlet) C++14
100 / 100
 1401 ms 74740 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 = n - 1; j >= 0; --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 512 KB Output is correct
2 Correct 888 ms 53880 KB Output is correct
3 Correct 885 ms 53752 KB Output is correct
4 Correct 723 ms 53688 KB Output is correct
5 Correct 775 ms 53328 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 617 ms 53880 KB Output is correct
2 Correct 752 ms 53624 KB Output is correct
3 Correct 900 ms 74104 KB Output is correct
4 Correct 1054 ms 74740 KB Output is correct
5 Correct 618 ms 53528 KB Output is correct
6 Correct 673 ms 60680 KB Output is correct
7 Correct 503 ms 44920 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 888 ms 53880 KB Output is correct
3 Correct 885 ms 53752 KB Output is correct
4 Correct 723 ms 53688 KB Output is correct
5 Correct 775 ms 53328 KB Output is correct
6 Correct 617 ms 53880 KB Output is correct
7 Correct 752 ms 53624 KB Output is correct
8 Correct 900 ms 74104 KB Output is correct
9 Correct 1054 ms 74740 KB Output is correct
10 Correct 618 ms 53528 KB Output is correct
11 Correct 673 ms 60680 KB Output is correct
12 Correct 503 ms 44920 KB Output is correct
13 Correct 840 ms 54648 KB Output is correct
14 Correct 1401 ms 61560 KB Output is correct
15 Correct 668 ms 53624 KB Output is correct
16 Correct 730 ms 58236 KB Output is correct
17 Correct 719 ms 60180 KB Output is correct
18 Correct 634 ms 53752 KB Output is correct
19 Correct 907 ms 53640 KB Output is correct
20 Correct 764 ms 53640 KB Output is correct
21 Correct 937 ms 54392 KB Output is correct
22 Correct 860 ms 54008 KB Output is correct
23 Correct 966 ms 54520 KB Output is correct
24 Correct 780 ms 60792 KB Output is correct
25 Correct 710 ms 53756 KB Output is correct