제출 #234738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234738		amoo_safar	Izlet (COI19_izlet)	C++14	100 / 100	718 ms	53856 KiB

izlet

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 3e3 + 10;
const ll Inf = 1e9;
const ll Log = 30;

int n;
int sm[N], mk[N], dis[N][N], c[N];
vector<int> G[N];
vector<pll> E;

void Mark(int u){
	mk[u] = 1;
	for(int v = 1; v <= n; v++) if(!mk[v]) sm[v] += dis[u][v];
}

int sc, st;
void DFS(int u, int p){
	if(dis[sc][u] == dis[st][u]){
		c[sc] = c[u];
		return ;
	}
	for(auto adj : G[u]) if(adj != p) DFS(adj, u);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	//assert(T == 1);
	cin >> n;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> dis[i][j];
	
	sm[n + 1] = Inf;
	int mn;
	Mark(1); c[1] = 1;
	for(int it = 2; it <= n; it++){
		mn = n + 1;
		for(int i = 1; i <= n; i++) if(!mk[i] && sm[i] < sm[mn]) mn = i;
		for(int i = 1; i <= n; i++){
			if(dis[mn][i] == 1 && mk[i] == 1){
				c[mn] = c[i];
				E.pb({mn, i});
				G[mn].pb(i);
				G[i].pb(mn);
				Mark(mn);
				break;
			}
		}
		if(mk[mn]) continue;
		int u = -1;
		for(int i = 1; i <= n; i++) if(mk[i] == 1 && dis[mn][i] == 2) u = i;
		assert(u > 0);
		Mark(mn);
		c[mn] = it;
		E.pb({mn, u});
		G[mn].pb(u);
		G[u].pb(mn);

		sc = mn;
		st = u;
		DFS(st, sc);
	}
	//cerr << '\n';

	for(int i = 1; i <= n; i++) cout << c[i] << ' ';
	cout << '\n';
	for(auto x : E) cout << x.F << ' ' << x.S << '\n';
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57