Submission #836480

#	Time	Username	Problem	Language	Result	Execution time	Memory
836480		Liudas	City Mapping (NOI18_citymapping)	C++17	0 / 100	2 ms	468 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int get(int x){
	if(par[x] != x){
		return par[x] = get(par[x]);
	}
	return x;
}
void merge(int a, int b){
	par[a] = b;
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	if(Q == 500000){
		vector<vector<int>> tree;
		int p = 0;
		for(int i = 0; i < N; i ++){
			for(int j = i + 1; j < N; j ++){
				tree.push_back({get_distance(i, j), i, j});
			}
		}
		sort(tree.begin(), tree.end());
		for(auto i : tree){
			int a = i[0], b = i[1], c = i[2];
			if(get(b) != get(c)){
				merge(b,c);
				A[p] = b;
				B[p] = c;
				W[p++] = a; 
			}
		}
	}
	else{
		vector<pair<long long, long long>> dist(N, {0, 0});
		for(int i = 1; i < N; i ++){
			dist[i] = {get_distance(1, i + 1), i};
		}
		sort(dist.rbegin(), dist.rend());
		for(int i = 1; i < N; i ++){
			dist[i] = {get_distance(dist[i].second + 1, dist[0].second + 1), dist[i].second};
		}
		long long total = 0;
		dist[0] = {0, dist[0].second};
		sort(dist.begin(), dist.end());
		for(int i = 1; i < N; i ++){
			W[i-1] = dist[i].first - total;
			A[i-1] = dist[i-1].second + 1;
			B[i-1] = dist[i].second + 1;
			total += W[i-1];
			cout << A[i] << " " << B[i] << " " << W[i] << endl;
		}
	}
	return;
}

Compilation message (stderr)

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:20:33: warning: narrowing conversion of 'get_distance(i, j)' from 'long long int' to 'int' [-Wnarrowing]
   20 |     tree.push_back({get_distance(i, j), i, j});
      |                     ~~~~~~~~~~~~^~~~~~
citymapping.cpp:20:33: warning: narrowing conversion of 'get_distance(i, j)' from 'long long int' to 'int' [-Wnarrowing]

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43