Submission #253383

#	Time	Username	Problem	Language	Result	Execution time	Memory
253383		erray	Izlet (COI19_izlet)	C++14	0 / 100	576 ms	43952 KiB

izlet

#include<bits/stdc++.h>
 
using namespace std;
 
int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int type;
	cin >> type;
	int n;
	cin >> 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];
		}
	}
	cerr << "First Passed" << '\n';
	class dsu {
		public:

	  vector<int> par, ct;
		dsu(int sz) {
			par.resize(sz);
			iota(par.begin(), par.end(), 0);
			ct.resize(sz, 1);
		}
		int get_par(int nd) {
			return par[nd] = (nd == par[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;
		}
	};
	vector<pair<int, int>> edges;
	dsu g(n);
	vector<vector<int>> g2(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (adj[i][j] == 1 && g.Merge(i, j)) {
				edges.emplace_back(i, j);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (adj[i][j] == 2 && g.Merge(i, j)) {
				edges.emplace_back(i, j);
			}
		}
	}
	cerr << "Passed" << '\n';
	for (auto el : edges) {
		g2[el.first].push_back(el.second);
		g2[el.second].push_back(el.first);
	}
	vector<bool> vis(n); 
	vector<vector<int>> groups;
	for (int i = 0; i < n; ++i) {
		if (vis[i]) continue;
		groups.push_back(vector<int>(1, i));
		function<void(int, int)> dfs = [&](int nd, int par) {
			for (auto el : g2[nd]) {
				if (el == par) continue;
//				cerr << i << ' ' << nd << ' ' << el << ' ' << adj[i][nd] << ' ' << adj[i][el] << '\n';
				if (adj[i][nd] == adj[i][el]) {
					groups.back().push_back(el);
					vis[el] = true;
				}
				dfs(el, nd);
			}
	  };
	  dfs(i, -1);
	}
	vector<int> col(n);
	cerr << (int) groups.size() << '\n';
	for (int i = 0; i < (int) groups.size(); ++i) {
		for (auto el : groups[i]) {
			col[el] = i + 1;
		}
	}
	for (auto el : col) cout << el << ' ';
	cout << '\n';
	for (auto& el : edges) cout << el.first + 1 << ' ' << el.second + 1 << '\n';
	cout << '\n';
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57