Submission #567578

#	Time	Username	Problem	Language	Result	Execution time	Memory
567578		CaroLinda	City Mapping (NOI18_citymapping)	C++14	100 / 100	19 ms	648 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
 
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
 
using namespace std ;
 
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	
	long long max_dist = 0 ;
	int rt = 2 ;
	for(int i= 2 ; i <= N ; i++ ){
		long long cur_dist = get_distance(i,1) ;
		if(cur_dist > max_dist){
			max_dist =cur_dist ;
			rt = i ;
		}
	}
	
	vector<long long> prof(N+1 , 0  ) ;
	for(int i = 1 ; i <= N ; i++ ){
		if(i != rt ) prof[i] = get_distance(i,rt) ;
	}
 
	vector<int> vertices(N) ; iota(all(vertices) , 1 ) ;
	sort(all(vertices) , [&](int a, int b){
		return prof[a] < prof[b] ;	
	}) ;
	
	vector<int> chainHead(N+1) ;
	vector<int> chainTail(N+1) ;
	vector<int> prox(N+1) ;
	vector<int> sub(N+1) ;
	vector<int> pai(N+1,-1) ;
	vector<long long> diam(N+1) ;
	vector< vector<int> > graph(N+1 , vector<int>()) ;
 	
	sub[rt] = 1 ;
	
	function<void(int)> makeChains = [&](int x){
		
		if(graph[x].empty()){
			chainTail[x] = x ;
			prox[x] = -1 ;
			diam[x] = 0 ;
			return ;
		}
		if(sz(graph[x]) > 1 && sub[graph[x][1]] > sub[graph[x][0]]){
			swap(graph[x][0] , graph[x][1]) ;
		}
		
		prox[x] = graph[x][0] ;
		chainHead[graph[x][0]] = chainHead[x] ;
		makeChains(prox[x]) ;
		chainTail[x] = chainTail[prox[x]] ;
		diam[x] = diam[prox[x]]-prof[x]+prof[prox[x]] ;
		
		if(sz(graph[x]) > 1 ){
			chainHead[graph[x][1]] = graph[x][1] ;
			makeChains(graph[x][1]) ;
		}
		
	} ;
	
	int idAns = -1 ;
	
	auto add = [&](int par, int son){
		
		idAns++ ;
		A[idAns] = par ;
		B[idAns] = son ;
		W[idAns] = prof[son]-prof[par];
		
		pai[son] = par ;
		graph[par].push_back(son) ;
		
		while(son != -1){
			sub[son]++ ;
			son = pai[son] ;
		}
			
	} ;
		
	for(int i = 1 , cur ; i < N ; i++ ){
		
		cur = vertices[i] ;
		chainHead[rt] = rt ;
		makeChains(rt) ;
				
		int p = rt ;
				
		while(true){
			long long X = prof[cur]-prof[p] ;
			long long Y = get_distance(cur, chainTail[p]) ;
			long long filete = X+Y-diam[p] ; filete >>= 1LL ;
			Y -= filete ;
			p = chainTail[p] ;
			while(diam[p] < Y) p = pai[p] ;
			if( sz(graph[p]) <= 1 ){
				add(p,cur) ;
				break ;
			}
			else{
				p = graph[p][1] ;
			}
		}
	}
 
}

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