oj.uz

Submission #1039361

# Submission time Handle Problem Language Result Execution time Memory
1039361 2024-07-30T19:00:24 Z mbfibat Izlet (COI19_izlet) C++17
100 / 100
 419 ms 74836 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) {
//		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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 311 ms 53584 KB Output is correct
3 Correct 307 ms 53588 KB Output is correct
4 Correct 331 ms 53328 KB Output is correct
5 Correct 419 ms 53332 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 53588 KB Output is correct
2 Correct 354 ms 53588 KB Output is correct
3 Correct 418 ms 73832 KB Output is correct
4 Correct 410 ms 74836 KB Output is correct
5 Correct 317 ms 53584 KB Output is correct
6 Correct 350 ms 60488 KB Output is correct
7 Correct 270 ms 49380 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 311 ms 53584 KB Output is correct
3 Correct 307 ms 53588 KB Output is correct
4 Correct 331 ms 53328 KB Output is correct
5 Correct 419 ms 53332 KB Output is correct
6 Correct 347 ms 53588 KB Output is correct
7 Correct 354 ms 53588 KB Output is correct
8 Correct 418 ms 73832 KB Output is correct
9 Correct 410 ms 74836 KB Output is correct
10 Correct 317 ms 53584 KB Output is correct
11 Correct 350 ms 60488 KB Output is correct
12 Correct 270 ms 49380 KB Output is correct
13 Correct 353 ms 54492 KB Output is correct
14 Correct 409 ms 61520 KB Output is correct
15 Correct 321 ms 53588 KB Output is correct
16 Correct 381 ms 57940 KB Output is correct
17 Correct 376 ms 59908 KB Output is correct
18 Correct 324 ms 53588 KB Output is correct
19 Correct 327 ms 53632 KB Output is correct
20 Correct 323 ms 53584 KB Output is correct
21 Correct 341 ms 54276 KB Output is correct
22 Correct 333 ms 53844 KB Output is correct
23 Correct 342 ms 54356 KB Output is correct
24 Correct 378 ms 60512 KB Output is correct
25 Correct 322 ms 53616 KB Output is correct