Submission #586367

#	Time	Username	Problem	Language	Result	Execution time	Memory
586367		Jomnoi	City Mapping (NOI18_citymapping)	C++17	57 / 100	129 ms	24656 KiB

citymapping

#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

const int MAX_N = 1005;

long long dist[MAX_N][MAX_N];
vector <pair <long long, int>> graph[MAX_N];
vector <tuple <int, int, int>> tree;
bool visited[MAX_N];

void dfs(int u, int p) {
	visited[u] = true;
	if(p != -1) {
		tree.emplace_back(u, p, dist[u][p]);
	}
	for(auto [w, v] : graph[u]) {
		if(visited[v] == true) {
			continue;
		}

		if(p == -1) {
			dfs(v, u);
		}
		else {
			if(dist[v][u] + dist[u][p] == dist[v][p]) {
				dfs(v, u);
			}
		}
	}
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	if(Q == 500000) {
		for(int i = 1; i <= N; i++) {
			for(int j = i + 1; j <= N; j++) {
				dist[i][j] = dist[j][i] = get_distance(i, j);
				graph[i].emplace_back(dist[i][j], j);
				graph[j].emplace_back(dist[j][i], i);
			}
		}

		for(int i = 1; i <= N; i++) {
			sort(graph[i].begin(), graph[i].end());
		}

		dfs(1, -1);
		
		for(int i = 0; i < N - 1; i++) {
			A[i] = get <0> (tree[i]);
			B[i] = get <1> (tree[i]);
			W[i] = get <2> (tree[i]);
		}
	}
	else if(Q == 12000) {
		int node = 1;
		long long furthest = 0;
		for(int i = 2; i <= N; i++) {
			dist[1][i] = get_distance(1, i);
			if(furthest < dist[1][i]) {
				furthest = dist[1][i];
				node = i;
			}
		}

		vector <pair <long long, int>> adj;
		for(int i = 1; i <= N; i++) {
			if(i == node) {
				continue;
			}

			dist[node][i] = get_distance(node, i);
			adj.emplace_back(dist[node][i], i);
		}

		sort(adj.begin(), adj.end());

		int prv = node, M = 0;
		long long prvDist = 0;
		for(auto [nowDist, now] : adj) {
			A[M] = prv;
			B[M] = now;
			W[M] = nowDist - prvDist;
			M++;
			
			prvDist = nowDist;
			prv = now;
		}
	}
	else {
		// do something
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 0 / 43