oj.uz

답안 #93514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93514 2019-01-09T07:34:45 Z admin City Mapping (NOI18_citymapping) C++17
25 / 100
 39 ms 508 KB 
#include "citymapping.h"

#include <bits/stdc++.h>

using namespace std;

using lint = long long;
using pil = pair<int, long long>;

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	const int ROOT = 1;
	
	vector<lint> dist_to_root(N+1);
	for(int u = 1; u <= N; u++) {
		if(u != ROOT) dist_to_root[u] = get_distance(ROOT, u);
	}

	vector<int> internal(N);
	iota(internal.begin(), internal.end(), 1);
	sort(internal.begin(), internal.end(), [&](const int &p, const int &q) {
		return dist_to_root[p] < dist_to_root[q];
	});
	
	int e = 0;
	for(unsigned i = 1; i < internal.size(); i++) {
		int u = internal[i];
		int v = -1; lint d = 1e18;
		for(unsigned j = 0; j < i; j++) {
			int p = internal[j];
			lint c = (j == 0) ? dist_to_root[u] : get_distance(u, p);
			if(v == -1 || d > c) {
				d = c;
				v = p;
			}
		}
		A[e] = u; B[e] = v; W[e] = d;
		e += 1;
	}
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 504 KB Correct: 498501 out of 500000 queries used.
2 Correct 34 ms 504 KB Correct: 499500 out of 500000 queries used.
3 Correct 25 ms 504 KB Correct: 492528 out of 500000 queries used.
4 Correct 22 ms 504 KB Correct: 494515 out of 500000 queries used.
5 Correct 28 ms 504 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 504 KB Correct: 498501 out of 500000 queries used.
2 Correct 34 ms 504 KB Correct: 499500 out of 500000 queries used.
3 Correct 25 ms 504 KB Correct: 492528 out of 500000 queries used.
4 Correct 22 ms 504 KB Correct: 494515 out of 500000 queries used.
5 Correct 28 ms 504 KB Correct: 498501 out of 500000 queries used.
6 Correct 28 ms 504 KB Correct: 495510 out of 500000 queries used.
7 Correct 36 ms 508 KB Correct: 497503 out of 500000 queries used.
8 Correct 29 ms 504 KB Correct: 497503 out of 500000 queries used.
9 Correct 27 ms 504 KB Correct: 495510 out of 500000 queries used.
10 Correct 34 ms 504 KB Correct: 496506 out of 500000 queries used.

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 504 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 504 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 504 KB Correct: 498501 out of 500000 queries used.
2 Correct 34 ms 504 KB Correct: 499500 out of 500000 queries used.
3 Correct 25 ms 504 KB Correct: 492528 out of 500000 queries used.
4 Correct 22 ms 504 KB Correct: 494515 out of 500000 queries used.
5 Correct 28 ms 504 KB Correct: 498501 out of 500000 queries used.
6 Correct 28 ms 504 KB Correct: 495510 out of 500000 queries used.
7 Correct 36 ms 508 KB Correct: 497503 out of 500000 queries used.
8 Correct 29 ms 504 KB Correct: 497503 out of 500000 queries used.
9 Correct 27 ms 504 KB Correct: 495510 out of 500000 queries used.
10 Correct 34 ms 504 KB Correct: 496506 out of 500000 queries used.
11 Incorrect 3 ms 504 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -