oj.uz

Submission #836620

# Submission time Handle Problem Language Result Execution time Memory
836620 2023-08-24T13:27:28 Z Liudas City Mapping (NOI18_citymapping) C++17
57 / 100
 26 ms 724 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
	vector<long long> childs;
	vector<long long> dists;
};
void dfs(int head, int par, long long dist, vector<node> &tree, vector<int> &good, long long d){
	if((tree[head].childs.size() <= 2) && d < dist){
		good.push_back(head);
	}
	for(int i = 0; i < tree[head].childs.size(); i ++){
		if(tree[head].childs[i] == par)continue;
		dfs(tree[head].childs[i], head, dist, tree, good, d + tree[head].dists[i]);
	}
}
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);
	picks[0] = -1e9;
	vector <long long> ends;
	ends.push_back(1);
	vector<node> arr(N + 20);
	for(auto [j, i] : tree){
		sort(ends.begin(), ends.end(), [&](long long a, long long b){return init[a] < init[b];});
		long long t = get_distance(ends.back(), i);
		vector<int> good;
		dfs(ends.back(), -1, t, arr, good, 0);
		sort(good.begin(), good.end(), [&](long long a, long long b){return init[a] > init[b];});
		for(auto r : good){
			long long t = get_distance(r, i);
			if(init[i] == init[r] + t){
				A[p] = i;
				B[p] = r;
				W[p++] = t;
				picks[r]++;
				ends.push_back(i);
				arr[r].childs.push_back(i);
				arr[r].dists.push_back(t);
				arr[i].childs.push_back(r);
				arr[i].dists.push_back(t);
				break;
			}
		}
	}
	return;
}

Compilation message

citymapping.cpp: In function 'void dfs(int, int, long long int, std::vector<node>&, std::vector<int>&, long long int)':
citymapping.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < tree[head].childs.size(); i ++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 596 KB Correct: 4157 out of 500000 queries used.
2 Correct 15 ms 596 KB Correct: 4072 out of 500000 queries used.
3 Correct 14 ms 596 KB Correct: 31822 out of 500000 queries used.
4 Correct 12 ms 596 KB Correct: 47490 out of 500000 queries used.
5 Correct 23 ms 580 KB Correct: 12042 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 596 KB Correct: 4157 out of 500000 queries used.
2 Correct 15 ms 596 KB Correct: 4072 out of 500000 queries used.
3 Correct 14 ms 596 KB Correct: 31822 out of 500000 queries used.
4 Correct 12 ms 596 KB Correct: 47490 out of 500000 queries used.
5 Correct 23 ms 580 KB Correct: 12042 out of 500000 queries used.
6 Correct 10 ms 596 KB Correct: 3013 out of 500000 queries used.
7 Correct 21 ms 596 KB Correct: 111842 out of 500000 queries used.
8 Correct 20 ms 596 KB Correct: 44465 out of 500000 queries used.
9 Correct 20 ms 596 KB Correct: 74230 out of 500000 queries used.
10 Correct 26 ms 548 KB Correct: 14553 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 724 KB Correct: 3141 out of 12000 queries used.
2 Correct 12 ms 596 KB Correct: 3524 out of 12000 queries used.
3 Correct 15 ms 596 KB Correct: 3804 out of 12000 queries used.
4 Correct 14 ms 596 KB Correct: 3768 out of 12000 queries used.
5 Correct 11 ms 596 KB Correct: 3408 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 724 KB Correct: 3141 out of 12000 queries used.
2 Correct 12 ms 596 KB Correct: 3524 out of 12000 queries used.
3 Correct 15 ms 596 KB Correct: 3804 out of 12000 queries used.
4 Correct 14 ms 596 KB Correct: 3768 out of 12000 queries used.
5 Correct 11 ms 596 KB Correct: 3408 out of 12000 queries used.
6 Correct 19 ms 640 KB Correct: 3916 out of 12000 queries used.
7 Correct 16 ms 596 KB Correct: 3750 out of 12000 queries used.
8 Correct 12 ms 596 KB Correct: 3383 out of 12000 queries used.
9 Correct 12 ms 596 KB Correct: 3439 out of 12000 queries used.
10 Correct 14 ms 596 KB Correct: 3611 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 596 KB Correct: 4157 out of 500000 queries used.
2 Correct 15 ms 596 KB Correct: 4072 out of 500000 queries used.
3 Correct 14 ms 596 KB Correct: 31822 out of 500000 queries used.
4 Correct 12 ms 596 KB Correct: 47490 out of 500000 queries used.
5 Correct 23 ms 580 KB Correct: 12042 out of 500000 queries used.
6 Correct 10 ms 596 KB Correct: 3013 out of 500000 queries used.
7 Correct 21 ms 596 KB Correct: 111842 out of 500000 queries used.
8 Correct 20 ms 596 KB Correct: 44465 out of 500000 queries used.
9 Correct 20 ms 596 KB Correct: 74230 out of 500000 queries used.
10 Correct 26 ms 548 KB Correct: 14553 out of 500000 queries used.
11 Correct 14 ms 724 KB Correct: 3141 out of 12000 queries used.
12 Correct 12 ms 596 KB Correct: 3524 out of 12000 queries used.
13 Correct 15 ms 596 KB Correct: 3804 out of 12000 queries used.
14 Correct 14 ms 596 KB Correct: 3768 out of 12000 queries used.
15 Correct 11 ms 596 KB Correct: 3408 out of 12000 queries used.
16 Correct 19 ms 640 KB Correct: 3916 out of 12000 queries used.
17 Correct 16 ms 596 KB Correct: 3750 out of 12000 queries used.
18 Correct 12 ms 596 KB Correct: 3383 out of 12000 queries used.
19 Correct 12 ms 596 KB Correct: 3439 out of 12000 queries used.
20 Correct 14 ms 596 KB Correct: 3611 out of 12000 queries used.
21 Correct 20 ms 596 KB Correct: 3940 out of 25000 queries used.
22 Incorrect 6 ms 596 KB Too many calls to get_distance().
23 Halted 0 ms 0 KB -