oj.uz

Submission #1039350

# Submission time Handle Problem Language Result Execution time Memory
1039350 2024-07-30T18:49:01 Z mbfibat Izlet (COI19_izlet) C++17
0 / 100
 574 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef pair<ii, ii> iv;

const int N = 3011;
int d[N][N];
vector<int> adj[N];

int n;

int par[N];
int anc(int x) {
	if (par[x] == x) return x;
	return par[x] = anc(par[x]);
}

void join(int x, int y) {
	par[anc(x)] = anc(y);
}

int col[N];
bool mark[N], done[N];

void trace(int org, int u, int pre = -1, int cur = 1) {
	if (d[org][u] > cur) {
		mark[col[u]] = true;
		++cur;
	}
	for (int v : adj[u])
		if (done[v] && v != pre)
			trace(org, v, u, cur);		
}

void dfs(int u, int p = 0) {
	for (int i = 1; i <= n; i++)
		mark[i] = false;
	trace(u, u);
	for (int i = 1; i <= n; i++)
		if (!mark[i]) {
			col[u] = i;
			break;
		}	

	done[u] = true;
	for (int v : adj[u])
		if (v != p)
			dfs(v, u);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int _; cin >> _;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> d[i][j];
	
	for (int i = 1; i <= n; i++)
		par[i] = i;

	for (int i = 1; i <= n; i++)	
		for (int j = i + 1; j <= n; j++)
			if (d[i][j] == 1) {
				join(i, j);
				adj[i].push_back(j);
				adj[j].push_back(i);
			}	


	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (d[i][j] > 1 && (anc(i) != anc(j))) {
				join(i, j);
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
	dfs(1);                 
//	cout << n << '\n';
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= n; j++)
//			cout << d[i][j] << " \n"[j == n];

//	cout << "--------------------------------" << '\n';

	for (int i = 1; i <= n; i++)
		cout << col[i] << (i < n ? " " : "");
	cout << '\n';	

	int cnt = 0;
	for (int i = 1; i <= n; i++)	
		for (int v : adj[i])
			if (v > i) {
				++cnt;
				cout << i << ' ' << v << (cnt < n - 1 ? "\n" : "");
			}
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 250 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 574 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 250 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -