Submission #253523

#	Time	Username	Problem	Language	Result	Execution time	Memory
253523		erray	Izlet (COI19_izlet)	C++14	43 / 100	1251 ms	465784 KiB

izlet

#include<bits/stdc++.h>
 
using namespace std;
#define int long long 
int32_t 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 mn {
		int source, l, r;
	};
	vector<vector<mn>> ct(n);
	for (int i = 0; i < n; ++i) {
		vector<int> len(n);
		function<void(int, int)> dfs = [&](int nd, int par) {
			assert(len[nd] < n);
	  	for (auto el : g2[nd]) {
	  		if (el == par) continue;
	  		len[el] = len[nd] + 1;	  		
	  		if (adj[i][nd] == adj[i][el]) {
	  			ct[len[el]].push_back(mn{i, nd, el});
	  		}          
	  		dfs(el, nd);
	  	}
		};
		dfs(i, -1);
	}
	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.source, el.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: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 0 / 57