oj.uz

Submission #836688

# Submission time Handle Problem Language Result Execution time Memory
836688 2023-08-24T14:02:29 Z Liudas City Mapping (NOI18_citymapping) C++17
9 / 100
 19 ms 8492 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<vector<long long>> init(N+5,vector<long long>(N+5));
	int p = 0;
	for(int i = 1; i < N; i ++){
		tree.push_back({get_distance(1, i+1), i+1});
		init[1][i+1] = tree.back().first;
		init[i+1][1] = tree.back().first;
	}
	sort(tree.begin(), tree.end());
	vector<node> arr(N + 20);
	for(auto [j, i] : tree){
		int head = 1;
		bool taken;
		int t;
		int ans = init[head][i];
		while(arr[head].childs.size()){
			taken = false;
			for(int k = 0; k < arr[head].childs.size(); k ++){
				t = get_distance(arr[head].childs[k], i);
				//cout << t << " " << arr[head].childs[k] << " " << i << " " << init[1][arr[head].childs[k]] << " " << init[1][i] <<  endl;
				if(init[1][arr[head].childs[k]] + t == init[1][i]){
					ans = t;
					head = arr[head].childs[k];
					taken = true;
					break;
				}
			}
			if(!taken){
				break;
			}
		}
		A[p] = head;
		B[p] = i;
		W[p++] = ans;
		arr[head].childs.push_back(i);
		init[i][head] = ans;
		init[head][i] = ans;
	}
	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 ++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int k = 0; k < arr[head].childs.size(); k ++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8404 KB Correct: 251481 out of 500000 queries used.
2 Correct 18 ms 8492 KB Correct: 308832 out of 500000 queries used.
3 Correct 5 ms 8276 KB Correct: 27160 out of 500000 queries used.
4 Correct 4 ms 8404 KB Correct: 21473 out of 500000 queries used.
5 Correct 5 ms 8404 KB Correct: 43091 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8404 KB Correct: 251481 out of 500000 queries used.
2 Correct 18 ms 8492 KB Correct: 308832 out of 500000 queries used.
3 Correct 5 ms 8276 KB Correct: 27160 out of 500000 queries used.
4 Correct 4 ms 8404 KB Correct: 21473 out of 500000 queries used.
5 Correct 5 ms 8404 KB Correct: 43091 out of 500000 queries used.
6 Incorrect 19 ms 8404 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8276 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8276 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8404 KB Correct: 251481 out of 500000 queries used.
2 Correct 18 ms 8492 KB Correct: 308832 out of 500000 queries used.
3 Correct 5 ms 8276 KB Correct: 27160 out of 500000 queries used.
4 Correct 4 ms 8404 KB Correct: 21473 out of 500000 queries used.
5 Correct 5 ms 8404 KB Correct: 43091 out of 500000 queries used.
6 Incorrect 19 ms 8404 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -