제출 #234914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234914		Saboon	Izlet (COI19_izlet)	C++14	100 / 100	921 ms	93352 KiB

izlet

#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 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57