oj.uz

Submission #253528

# Submission time Handle Problem Language Result Execution time Memory
253528 2020-07-28T07:02:54 Z erray Izlet (COI19_izlet) C++17
43 / 100
 1084 ms 233108 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);
	struct same { int sr, l, r; };
	vector<vector<same>> ct(n);
	for (int i = 0; i < n; ++i) {
		vector<int> len(n);
		function<void(int, int)> dfs = [&](int nd, int par) {
			for (auto el : g[nd]) {
				if (el == par) continue;
				len[el] = len[nd] + 1;
				if (adj[i][el] == adj[i][nd]) {
					ct[len[el]].push_back(same{i, nd, el});
				}
				dfs(el, nd);
			}
		};
		dfs(i, -1);		
	}
	dsu col(n);
	vector<vector<bool>> vis(n, vector<bool>(n));
	for (int i = 0; i < n; ++i) {
		for (auto el : ct[i]) {
			if (vis[el.l][el.r]) continue;
			vis[el.l][el.r] = true;       	
			col.Merge(el.sr, el.r);		  	
		}
	}
	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 890 ms 233108 KB Output is correct
3 Correct 987 ms 233064 KB Output is correct
4 Correct 1034 ms 214876 KB Output is correct
5 Correct 903 ms 174696 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 178456 KB Output is correct
2 Correct 1027 ms 202232 KB Output is correct
3 Correct 1039 ms 78712 KB Output is correct
4 Correct 934 ms 37880 KB Output is correct
5 Correct 898 ms 168736 KB Output is correct
6 Correct 974 ms 180776 KB Output is correct
7 Correct 708 ms 111056 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 890 ms 233108 KB Output is correct
3 Correct 987 ms 233064 KB Output is correct
4 Correct 1034 ms 214876 KB Output is correct
5 Correct 903 ms 174696 KB Output is correct
6 Correct 1018 ms 178456 KB Output is correct
7 Correct 1027 ms 202232 KB Output is correct
8 Correct 1039 ms 78712 KB Output is correct
9 Correct 934 ms 37880 KB Output is correct
10 Correct 898 ms 168736 KB Output is correct
11 Correct 974 ms 180776 KB Output is correct
12 Correct 708 ms 111056 KB Output is correct
13 Incorrect 1084 ms 127524 KB Output isn't correct
14 Halted 0 ms 0 KB -