oj.uz

Submission #253519

# Submission time Handle Problem Language Result Execution time Memory
253519 2020-07-28T06:40:41 Z erray Izlet (COI19_izlet) C++14
43 / 100
 1033 ms 233488 KB 
#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 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 1022 ms 233488 KB Output is correct
3 Correct 980 ms 233380 KB Output is correct
4 Correct 1002 ms 232344 KB Output is correct
5 Correct 1027 ms 192060 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 178424 KB Output is correct
2 Correct 1022 ms 220284 KB Output is correct
3 Correct 984 ms 116984 KB Output is correct
4 Correct 857 ms 76248 KB Output is correct
5 Correct 911 ms 186400 KB Output is correct
6 Correct 928 ms 204932 KB Output is correct
7 Correct 658 ms 129416 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 1022 ms 233488 KB Output is correct
3 Correct 980 ms 233380 KB Output is correct
4 Correct 1002 ms 232344 KB Output is correct
5 Correct 1027 ms 192060 KB Output is correct
6 Correct 1002 ms 178424 KB Output is correct
7 Correct 1022 ms 220284 KB Output is correct
8 Correct 984 ms 116984 KB Output is correct
9 Correct 857 ms 76248 KB Output is correct
10 Correct 911 ms 186400 KB Output is correct
11 Correct 928 ms 204932 KB Output is correct
12 Correct 658 ms 129416 KB Output is correct
13 Incorrect 1033 ms 146288 KB Output isn't correct
14 Halted 0 ms 0 KB -