Submission #253523

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
253523	2020-07-28T06:46:21 Z	erray	Izlet (COI19_izlet)	C++14	43 / 100	1251 ms	465784 KB

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.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1134 ms	465784 KB	Output is correct
3	Correct	1110 ms	465652 KB	Output is correct
4	Correct	1150 ms	429180 KB	Output is correct
5	Correct	1194 ms	348476 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1251 ms	330544 KB	Output is correct
2	Correct	1172 ms	404128 KB	Output is correct
3	Correct	1105 ms	152560 KB	Output is correct
4	Correct	852 ms	73208 KB	Output is correct
5	Correct	985 ms	338856 KB	Output is correct
6	Correct	983 ms	355128 KB	Output is correct
7	Correct	754 ms	219480 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	1134 ms	465784 KB	Output is correct
3	Correct	1110 ms	465652 KB	Output is correct
4	Correct	1150 ms	429180 KB	Output is correct
5	Correct	1194 ms	348476 KB	Output is correct
6	Correct	1251 ms	330544 KB	Output is correct
7	Correct	1172 ms	404128 KB	Output is correct
8	Correct	1105 ms	152560 KB	Output is correct
9	Correct	852 ms	73208 KB	Output is correct
10	Correct	985 ms	338856 KB	Output is correct
11	Correct	983 ms	355128 KB	Output is correct
12	Correct	754 ms	219480 KB	Output is correct
13	Incorrect	1229 ms	255092 KB	Output isn't correct
14	Halted	0 ms	0 KB	-