oj.uz

Submission #972928

# Submission time Handle Problem Language Result Execution time Memory
972928 2024-05-01T10:27:46 Z NoMercy City Mapping (NOI18_citymapping) C++17
57 / 100
 8 ms 856 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pair<ll , int>> v;
	v.push_back({0LL , 1});
	for (int i = 2;i <= N;i ++) {
		ll w = get_distance(1 , i);
		v.push_back({w , i});
	}
	sort(v.begin() , v.end());
	int ind = 0;
	for (int i = 1;i < N;i ++) {
		if (ind == N - 1) {
			break;
		}
		for (int j = i - 1;j >= 0;j --) {
			ll w = v[i].first - v[j].first;
			if (j >= 1) {
				w = get_distance(v[i].second , v[j].second);
			}
			if (w == v[i].first - v[j].first) {
				A[ind] = min(v[i].second , v[j].second);
				B[ind] = max(v[i].second , v[j].second);
				W[ind] = w;
				ind ++;
				break;
			}
		}
	}
	return;
}
/*

5 50000 5
1 4 8
2 4 1
3 4 7
3 5 3

*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 2916 out of 500000 queries used.
2 Correct 1 ms 600 KB Correct: 3406 out of 500000 queries used.
3 Correct 5 ms 604 KB Correct: 68050 out of 500000 queries used.
4 Correct 5 ms 604 KB Correct: 116897 out of 500000 queries used.
5 Correct 3 ms 376 KB Correct: 20876 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 2916 out of 500000 queries used.
2 Correct 1 ms 600 KB Correct: 3406 out of 500000 queries used.
3 Correct 5 ms 604 KB Correct: 68050 out of 500000 queries used.
4 Correct 5 ms 604 KB Correct: 116897 out of 500000 queries used.
5 Correct 3 ms 376 KB Correct: 20876 out of 500000 queries used.
6 Correct 2 ms 856 KB Correct: 2016 out of 500000 queries used.
7 Correct 8 ms 600 KB Correct: 129253 out of 500000 queries used.
8 Correct 4 ms 604 KB Correct: 68450 out of 500000 queries used.
9 Correct 7 ms 628 KB Correct: 123220 out of 500000 queries used.
10 Correct 2 ms 604 KB Correct: 18026 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Correct: 2120 out of 12000 queries used.
2 Correct 1 ms 612 KB Correct: 2422 out of 12000 queries used.
3 Correct 1 ms 612 KB Correct: 2628 out of 12000 queries used.
4 Correct 1 ms 600 KB Correct: 2616 out of 12000 queries used.
5 Correct 1 ms 612 KB Correct: 2323 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Correct: 2120 out of 12000 queries used.
2 Correct 1 ms 612 KB Correct: 2422 out of 12000 queries used.
3 Correct 1 ms 612 KB Correct: 2628 out of 12000 queries used.
4 Correct 1 ms 600 KB Correct: 2616 out of 12000 queries used.
5 Correct 1 ms 612 KB Correct: 2323 out of 12000 queries used.
6 Correct 2 ms 608 KB Correct: 2917 out of 12000 queries used.
7 Correct 2 ms 608 KB Correct: 2753 out of 12000 queries used.
8 Correct 1 ms 608 KB Correct: 2382 out of 12000 queries used.
9 Correct 1 ms 608 KB Correct: 2441 out of 12000 queries used.
10 Correct 1 ms 608 KB Correct: 2616 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 2916 out of 500000 queries used.
2 Correct 1 ms 600 KB Correct: 3406 out of 500000 queries used.
3 Correct 5 ms 604 KB Correct: 68050 out of 500000 queries used.
4 Correct 5 ms 604 KB Correct: 116897 out of 500000 queries used.
5 Correct 3 ms 376 KB Correct: 20876 out of 500000 queries used.
6 Correct 2 ms 856 KB Correct: 2016 out of 500000 queries used.
7 Correct 8 ms 600 KB Correct: 129253 out of 500000 queries used.
8 Correct 4 ms 604 KB Correct: 68450 out of 500000 queries used.
9 Correct 7 ms 628 KB Correct: 123220 out of 500000 queries used.
10 Correct 2 ms 604 KB Correct: 18026 out of 500000 queries used.
11 Correct 2 ms 604 KB Correct: 2120 out of 12000 queries used.
12 Correct 1 ms 612 KB Correct: 2422 out of 12000 queries used.
13 Correct 1 ms 612 KB Correct: 2628 out of 12000 queries used.
14 Correct 1 ms 600 KB Correct: 2616 out of 12000 queries used.
15 Correct 1 ms 612 KB Correct: 2323 out of 12000 queries used.
16 Correct 2 ms 608 KB Correct: 2917 out of 12000 queries used.
17 Correct 2 ms 608 KB Correct: 2753 out of 12000 queries used.
18 Correct 1 ms 608 KB Correct: 2382 out of 12000 queries used.
19 Correct 1 ms 608 KB Correct: 2441 out of 12000 queries used.
20 Correct 1 ms 608 KB Correct: 2616 out of 12000 queries used.
21 Correct 2 ms 600 KB Correct: 2943 out of 25000 queries used.
22 Incorrect 3 ms 612 KB Too many calls to get_distance().
23 Halted 0 ms 0 KB -