oj.uz

Submission #567564

# Submission time Handle Problem Language Result Execution time Memory
567564 2022-05-23T17:36:06 Z CaroLinda City Mapping (NOI18_citymapping) C++14
13 / 100
 2000 ms 680 KB 
#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 = 1000000000LL  * N + 1LL ;
	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<int> 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 680 KB Correct: 3506 out of 500000 queries used.
2 Incorrect 10 ms 472 KB Too many calls to get_distance().
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 680 KB Correct: 3506 out of 500000 queries used.
2 Incorrect 10 ms 472 KB Too many calls to get_distance().
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Correct: 3687 out of 12000 queries used.
2 Correct 18 ms 572 KB Correct: 2991 out of 12000 queries used.
3 Correct 16 ms 468 KB Correct: 3560 out of 12000 queries used.
4 Correct 15 ms 572 KB Correct: 3704 out of 12000 queries used.
5 Correct 16 ms 576 KB Correct: 3599 out of 12000 queries used.

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Correct: 3687 out of 12000 queries used.
2 Correct 18 ms 572 KB Correct: 2991 out of 12000 queries used.
3 Correct 16 ms 468 KB Correct: 3560 out of 12000 queries used.
4 Correct 15 ms 572 KB Correct: 3704 out of 12000 queries used.
5 Correct 16 ms 576 KB Correct: 3599 out of 12000 queries used.
6 Execution timed out 2075 ms 600 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 680 KB Correct: 3506 out of 500000 queries used.
2 Incorrect 10 ms 472 KB Too many calls to get_distance().
3 Halted 0 ms 0 KB -