oj.uz

답안 #836568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836568 2023-08-24T12:58:44 Z Liudas City Mapping (NOI18_citymapping) C++17
57 / 100
 33 ms 528 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pair<long long, long long>> tree;
	vector<long long> init(N+5);
	int p = 0;
	for(int i = 1; i < N; i ++){
		tree.push_back({get_distance(1, i+1), i+1});
		init[i+1] = tree.back().first;
	}
	sort(tree.begin(), tree.end());
	vector<int> picks(N+20);
	vector <long long> ends;
	for(auto [j, i] : tree){
		int picked = false;
		sort(ends.begin(), ends.end(), [&](long long a, long long b){return init[a] > init[b];});
		for(auto r : ends){
			long long t = get_distance(r, i);
			if(init[i] == init[r] + t){
				picked = true;
				A[p] = i;
				B[p] = r;
				W[p++] = t;
				picks[r]++;
				ends.push_back(i);
				if(picks[r] == 2){
					ends.erase(find(ends.begin(), ends.end(), r));
				}
				break;
			}
		}
		if(!picked){
			ends.push_back(i);
			A[p] = 1;
			B[p] = i;
			W[p++] = init[i];
		}
	}
	return;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 468 KB Correct: 2896 out of 500000 queries used.
2 Correct 15 ms 500 KB Correct: 3426 out of 500000 queries used.
3 Correct 15 ms 496 KB Correct: 62476 out of 500000 queries used.
4 Correct 8 ms 468 KB Correct: 106971 out of 500000 queries used.
5 Correct 21 ms 468 KB Correct: 20750 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 468 KB Correct: 2896 out of 500000 queries used.
2 Correct 15 ms 500 KB Correct: 3426 out of 500000 queries used.
3 Correct 15 ms 496 KB Correct: 62476 out of 500000 queries used.
4 Correct 8 ms 468 KB Correct: 106971 out of 500000 queries used.
5 Correct 21 ms 468 KB Correct: 20750 out of 500000 queries used.
6 Correct 23 ms 528 KB Correct: 2016 out of 500000 queries used.
7 Correct 20 ms 508 KB Correct: 128334 out of 500000 queries used.
8 Correct 17 ms 468 KB Correct: 64239 out of 500000 queries used.
9 Correct 23 ms 484 KB Correct: 111489 out of 500000 queries used.
10 Correct 32 ms 468 KB Correct: 17948 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 468 KB Correct: 2124 out of 12000 queries used.
2 Correct 23 ms 520 KB Correct: 2427 out of 12000 queries used.
3 Correct 24 ms 512 KB Correct: 2593 out of 12000 queries used.
4 Correct 24 ms 520 KB Correct: 2614 out of 12000 queries used.
5 Correct 24 ms 528 KB Correct: 2311 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 468 KB Correct: 2124 out of 12000 queries used.
2 Correct 23 ms 520 KB Correct: 2427 out of 12000 queries used.
3 Correct 24 ms 512 KB Correct: 2593 out of 12000 queries used.
4 Correct 24 ms 520 KB Correct: 2614 out of 12000 queries used.
5 Correct 24 ms 528 KB Correct: 2311 out of 12000 queries used.
6 Correct 33 ms 468 KB Correct: 2917 out of 12000 queries used.
7 Correct 24 ms 504 KB Correct: 2753 out of 12000 queries used.
8 Correct 23 ms 528 KB Correct: 2382 out of 12000 queries used.
9 Correct 23 ms 468 KB Correct: 2441 out of 12000 queries used.
10 Correct 23 ms 468 KB Correct: 2616 out of 12000 queries used.

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 468 KB Correct: 2896 out of 500000 queries used.
2 Correct 15 ms 500 KB Correct: 3426 out of 500000 queries used.
3 Correct 15 ms 496 KB Correct: 62476 out of 500000 queries used.
4 Correct 8 ms 468 KB Correct: 106971 out of 500000 queries used.
5 Correct 21 ms 468 KB Correct: 20750 out of 500000 queries used.
6 Correct 23 ms 528 KB Correct: 2016 out of 500000 queries used.
7 Correct 20 ms 508 KB Correct: 128334 out of 500000 queries used.
8 Correct 17 ms 468 KB Correct: 64239 out of 500000 queries used.
9 Correct 23 ms 484 KB Correct: 111489 out of 500000 queries used.
10 Correct 32 ms 468 KB Correct: 17948 out of 500000 queries used.
11 Correct 31 ms 468 KB Correct: 2124 out of 12000 queries used.
12 Correct 23 ms 520 KB Correct: 2427 out of 12000 queries used.
13 Correct 24 ms 512 KB Correct: 2593 out of 12000 queries used.
14 Correct 24 ms 520 KB Correct: 2614 out of 12000 queries used.
15 Correct 24 ms 528 KB Correct: 2311 out of 12000 queries used.
16 Correct 33 ms 468 KB Correct: 2917 out of 12000 queries used.
17 Correct 24 ms 504 KB Correct: 2753 out of 12000 queries used.
18 Correct 23 ms 528 KB Correct: 2382 out of 12000 queries used.
19 Correct 23 ms 468 KB Correct: 2441 out of 12000 queries used.
20 Correct 23 ms 468 KB Correct: 2616 out of 12000 queries used.
21 Correct 24 ms 496 KB Correct: 2943 out of 25000 queries used.
22 Incorrect 5 ms 468 KB Too many calls to get_distance().
23 Halted 0 ms 0 KB -