Submission #1039361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039361		mbfibat	Izlet (COI19_izlet)	C++17	100 / 100	419 ms	74836 KiB

izlet

#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) {
//		cerr << '!' << d[org][u] << ' ' << cur << ' ' << u << ' ' << col[u] << '\n';
		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]) {          
//			cerr << u << ' ' << i << '\n';
			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 && (anc(i) != anc(j))) {
				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] == 2 && (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: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57