oj.uz

Submission #234914

# Submission time Handle Problem Language Result Execution time Memory
234914 2020-05-26T08:53:16 Z Saboon Izlet (COI19_izlet) C++14
100 / 100
 921 ms 93352 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;

const int maxn = 3000 + 10;

int n;
int dp[maxn], d[maxn][maxn], par[maxn], dis[maxn][maxn];
bool mark[maxn];
int c[maxn], cnt = 1;
vector<int> t[maxn];

void dfs(int v){
	int w = -1;
	for (int u = 1; u <= n; u++)
		if (mark[u] and d[v][u] == d[par[v]][u] and (w == -1 or dis[v][u] < dis[v][w]))
			w = u;
	mark[v] = 1;
	if (w == -1)
		c[v] = cnt ++;
	else
		c[v] = c[w];
	for (auto u : t[v])
		if (u != par[v])
			dfs(u);
}

void DFS(int v, int root, int p = -1){
	for (auto u : t[v])
		if (u != p)
			dis[root][u] = dis[root][v] + 1, DFS(u, root, v);
}

int main(){
	ios_base::sync_with_stdio(false);
	int chert;
	cin >> chert >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> d[i][j];
	memset(dp, 63, sizeof dp);
	dp[1] = 0;
	for (int _ = 1; _ <= n; _++){
		int v = -1;
		for (int u = 1; u <= n; u++)
			if (!mark[u] and (v == -1 or dp[u] < dp[v]))
				v = u;
		if (v != 1){
			t[par[v]].push_back(v);
			t[v].push_back(par[v]);
		}
		mark[v] = 1;
		for (int u = 1; u <= n; u++)
			if (!mark[u] and dp[u] > d[u][v])
				dp[u] = d[u][v], par[u] = v;
	}
	for (int v = 1; v <= n; v++)
		dis[v][v] = 1, DFS(v, v);
	memset(mark, 0, sizeof mark);
	dfs(1);
	for (int i = 1; i <= n; i++)
		cout << c[i] << " \n"[i == n];
	for (int i = 2; i <= n; i++)
		cout << par[i] << " " << i << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 723 ms 71328 KB Output is correct
3 Correct 717 ms 71416 KB Output is correct
4 Correct 698 ms 71160 KB Output is correct
5 Correct 725 ms 71288 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 71548 KB Output is correct
2 Correct 751 ms 88920 KB Output is correct
3 Correct 892 ms 88184 KB Output is correct
4 Correct 921 ms 81532 KB Output is correct
5 Correct 734 ms 72440 KB Output is correct
6 Correct 744 ms 78584 KB Output is correct
7 Correct 551 ms 61944 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 723 ms 71328 KB Output is correct
3 Correct 717 ms 71416 KB Output is correct
4 Correct 698 ms 71160 KB Output is correct
5 Correct 725 ms 71288 KB Output is correct
6 Correct 696 ms 71548 KB Output is correct
7 Correct 751 ms 88920 KB Output is correct
8 Correct 892 ms 88184 KB Output is correct
9 Correct 921 ms 81532 KB Output is correct
10 Correct 734 ms 72440 KB Output is correct
11 Correct 744 ms 78584 KB Output is correct
12 Correct 551 ms 61944 KB Output is correct
13 Correct 819 ms 72852 KB Output is correct
14 Correct 875 ms 78584 KB Output is correct
15 Correct 775 ms 72440 KB Output is correct
16 Correct 858 ms 93352 KB Output is correct
17 Correct 861 ms 78376 KB Output is correct
18 Correct 679 ms 81144 KB Output is correct
19 Correct 735 ms 81568 KB Output is correct
20 Correct 743 ms 81272 KB Output is correct
21 Correct 792 ms 72812 KB Output is correct
22 Correct 741 ms 72312 KB Output is correct
23 Correct 788 ms 72696 KB Output is correct
24 Correct 865 ms 78140 KB Output is correct
25 Correct 765 ms 72440 KB Output is correct