제출 #146981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146981		gs14004	City Mapping (NOI18_citymapping)	C++17	57 / 100	22 ms	8568 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 1005;

lint mem[MAXN][MAXN];

lint dist(int x, int y){
	if(x == y) return 0;
	if(mem[x][y]) return mem[x][y];
	return mem[x][y] = mem[y][x] = get_distance(x, y);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	auto make_edge = [&](int s, int e, int x){
		for(int i=0; i<N-1; i++){
			if(!W[i]){
				tie(A[i], B[i], W[i]) = make_tuple(s, e, x);
				break;
			}
		}
	};
	vector<pi> v;
	for(int i=2; i<=N; i++) v.emplace_back(dist(1, i), i);
	sort(v.begin(), v.end());
	vector<int> prv = {1};
	for(auto &i : v){
		for(int j=sz(prv)-1; j>=0; j--){
			if(dist(1, prv[j]) + dist(prv[j], i.second) == i.first){
				make_edge(prv[j], i.second, dist(prv[j], i.second));
				break;
			}
		}
		prv.push_back(i.second);
	}
}

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