Submission #836688

#	Time	Username	Problem	Language	Result	Execution time	Memory
836688		Liudas	City Mapping (NOI18_citymapping)	C++17	9 / 100	19 ms	8492 KiB

citymapping

#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 (stderr)

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 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43