Submission #253518

#	Time	Username	Problem	Language	Result	Execution time	Memory
253518		erray	Izlet (COI19_izlet)	C++14	0 / 100	2096 ms	316632 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);
	}
	dsu col(n);
	struct pq_el {
		int sp, source, l, r;
		bool operator< (const pq_el& ot) const {
			return sp > ot.sp;
		}
	};
	priority_queue<pq_el> pq;
	for (int i = 0; i < n; ++i) {
		vector<int> len(n);
		function<void(int, int)> dfs = [&](int nd, int par) {
	  	for (auto el : g2[nd]) {
	  		if (el == par) continue;
	  		len[el] = len[nd] + 1;	  		
	  		if (adj[i][nd] == adj[i][el]) {
					pq.emplace(pq_el{len[el], i, nd, el});	  		
	  		}          
	  		dfs(el, nd);
	  	}
		};
		dfs(i, -1);
	}
	vector<vector<bool>> vis(n, vector<bool>(n));
	while (!pq.empty()) {
		pq_el cur = pq.top();
		pq.pop();
//		cerr << cur.sp << ' ' << cur.source << ' ' << cur.l << ' ' << cur.r << '\n';
		if (vis[cur.l][cur.r]) continue;
		vis[cur.l][cur.r] = true;
		col.Merge(cur.source, cur.r);
	}
	for (int i = 0; i < n; ++i) {
		cout << col.get_par(i) + 1 << ' ';
	}
	cout << '\n';
	for (auto el : edges) cout << el.first + 1 << ' ' << el.second + 1 << '\n';
}

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