제출 #836243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836243		unnick	City Mapping (NOI18_citymapping)	C++14	41 / 100	43 ms	592 KiB

citymapping

#include "citymapping.h"

// #include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

#define ll long long

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	if (Q <= 12000) {
		int start;
		{
			ll maxd = 0;
			for (int i = 2; i <= N; i++) {
				ll d = get_distance(1, i);
				if (d > maxd) {
					maxd = d;
					start = i;
				}
			}
		}
		vector<ll> dists(N);
		dists[start-1] = 0;
		vector<int> ids(N);
		iota(ids.begin(), ids.end(), 0);
		for (int i = 1; i <= N; i++) {
			if (i == start) continue;
			dists[i-1] = get_distance(start,i);
		}
		sort(ids.begin(), ids.end(), [&](int a, int b) {
			return dists[a] < dists[b];
		});
		for (int i = 0; i < N-1; i++) {
			A[i] = ids[i]+1;
			B[i] = ids[i+1]+1;
			W[i] = dists[ids[i+1]] - dists[ids[i]];
		}
	} else {
		// vector<ll> dists(N*N);
		int k = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = i+1; j <= N; j++) {
				if (get_distance(i,j) == 1) {
					A[k] = i;
					B[k] = j;
					W[k++] = 1;
				}
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:31:29: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |    dists[i-1] = get_distance(start,i);
      |                 ~~~~~~~~~~~~^~~~~~~~~

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