oj.uz

Submission #146981

# Submission time Handle Problem Language Result Execution time Memory
146981 2019-08-27T02:24:51 Z gs14004 City Mapping (NOI18_citymapping) C++17
57 / 100
 22 ms 8568 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8056 KB Correct: 2916 out of 500000 queries used.
2 Correct 10 ms 8056 KB Correct: 3406 out of 500000 queries used.
3 Correct 14 ms 8312 KB Correct: 68050 out of 500000 queries used.
4 Correct 18 ms 8312 KB Correct: 116897 out of 500000 queries used.
5 Correct 11 ms 8312 KB Correct: 20876 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8056 KB Correct: 2916 out of 500000 queries used.
2 Correct 10 ms 8056 KB Correct: 3406 out of 500000 queries used.
3 Correct 14 ms 8312 KB Correct: 68050 out of 500000 queries used.
4 Correct 18 ms 8312 KB Correct: 116897 out of 500000 queries used.
5 Correct 11 ms 8312 KB Correct: 20876 out of 500000 queries used.
6 Correct 9 ms 7544 KB Correct: 2016 out of 500000 queries used.
7 Correct 22 ms 8312 KB Correct: 129253 out of 500000 queries used.
8 Correct 15 ms 8568 KB Correct: 68450 out of 500000 queries used.
9 Correct 19 ms 8312 KB Correct: 123220 out of 500000 queries used.
10 Correct 11 ms 8312 KB Correct: 18026 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Correct: 2120 out of 12000 queries used.
2 Correct 9 ms 7672 KB Correct: 2422 out of 12000 queries used.
3 Correct 9 ms 7800 KB Correct: 2628 out of 12000 queries used.
4 Correct 9 ms 7800 KB Correct: 2616 out of 12000 queries used.
5 Correct 9 ms 7544 KB Correct: 2323 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Correct: 2120 out of 12000 queries used.
2 Correct 9 ms 7672 KB Correct: 2422 out of 12000 queries used.
3 Correct 9 ms 7800 KB Correct: 2628 out of 12000 queries used.
4 Correct 9 ms 7800 KB Correct: 2616 out of 12000 queries used.
5 Correct 9 ms 7544 KB Correct: 2323 out of 12000 queries used.
6 Correct 10 ms 8056 KB Correct: 2917 out of 12000 queries used.
7 Correct 11 ms 8184 KB Correct: 2753 out of 12000 queries used.
8 Correct 9 ms 7672 KB Correct: 2382 out of 12000 queries used.
9 Correct 9 ms 7672 KB Correct: 2441 out of 12000 queries used.
10 Correct 9 ms 7800 KB Correct: 2616 out of 12000 queries used.

Subtask #5
0 / 43.0

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