oj.uz

Submission #567578

# Submission time Handle Problem Language Result Execution time Memory
567578 2022-05-23T17:48:04 Z CaroLinda City Mapping (NOI18_citymapping) C++14
100 / 100
 19 ms 648 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 = 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Correct: 2994 out of 500000 queries used.
2 Correct 16 ms 540 KB Correct: 3256 out of 500000 queries used.
3 Correct 16 ms 524 KB Correct: 5512 out of 500000 queries used.
4 Correct 15 ms 520 KB Correct: 6565 out of 500000 queries used.
5 Correct 19 ms 468 KB Correct: 3898 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Correct: 2994 out of 500000 queries used.
2 Correct 16 ms 540 KB Correct: 3256 out of 500000 queries used.
3 Correct 16 ms 524 KB Correct: 5512 out of 500000 queries used.
4 Correct 15 ms 520 KB Correct: 6565 out of 500000 queries used.
5 Correct 19 ms 468 KB Correct: 3898 out of 500000 queries used.
6 Correct 18 ms 524 KB Correct: 2985 out of 500000 queries used.
7 Correct 17 ms 568 KB Correct: 2992 out of 500000 queries used.
8 Correct 15 ms 468 KB Correct: 5385 out of 500000 queries used.
9 Correct 14 ms 528 KB Correct: 6096 out of 500000 queries used.
10 Correct 18 ms 468 KB Correct: 3924 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 568 KB Correct: 2970 out of 12000 queries used.
2 Correct 18 ms 468 KB Correct: 2976 out of 12000 queries used.
3 Correct 19 ms 484 KB Correct: 2997 out of 12000 queries used.
4 Correct 18 ms 568 KB Correct: 2976 out of 12000 queries used.
5 Correct 19 ms 560 KB Correct: 2970 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 568 KB Correct: 2970 out of 12000 queries used.
2 Correct 18 ms 468 KB Correct: 2976 out of 12000 queries used.
3 Correct 19 ms 484 KB Correct: 2997 out of 12000 queries used.
4 Correct 18 ms 568 KB Correct: 2976 out of 12000 queries used.
5 Correct 19 ms 560 KB Correct: 2970 out of 12000 queries used.
6 Correct 18 ms 556 KB Correct: 2991 out of 12000 queries used.
7 Correct 19 ms 468 KB Correct: 2985 out of 12000 queries used.
8 Correct 18 ms 576 KB Correct: 2997 out of 12000 queries used.
9 Correct 19 ms 468 KB Correct: 2988 out of 12000 queries used.
10 Correct 17 ms 548 KB Correct: 2979 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Correct: 2994 out of 500000 queries used.
2 Correct 16 ms 540 KB Correct: 3256 out of 500000 queries used.
3 Correct 16 ms 524 KB Correct: 5512 out of 500000 queries used.
4 Correct 15 ms 520 KB Correct: 6565 out of 500000 queries used.
5 Correct 19 ms 468 KB Correct: 3898 out of 500000 queries used.
6 Correct 18 ms 524 KB Correct: 2985 out of 500000 queries used.
7 Correct 17 ms 568 KB Correct: 2992 out of 500000 queries used.
8 Correct 15 ms 468 KB Correct: 5385 out of 500000 queries used.
9 Correct 14 ms 528 KB Correct: 6096 out of 500000 queries used.
10 Correct 18 ms 468 KB Correct: 3924 out of 500000 queries used.
11 Correct 18 ms 568 KB Correct: 2970 out of 12000 queries used.
12 Correct 18 ms 468 KB Correct: 2976 out of 12000 queries used.
13 Correct 19 ms 484 KB Correct: 2997 out of 12000 queries used.
14 Correct 18 ms 568 KB Correct: 2976 out of 12000 queries used.
15 Correct 19 ms 560 KB Correct: 2970 out of 12000 queries used.
16 Correct 18 ms 556 KB Correct: 2991 out of 12000 queries used.
17 Correct 19 ms 468 KB Correct: 2985 out of 12000 queries used.
18 Correct 18 ms 576 KB Correct: 2997 out of 12000 queries used.
19 Correct 19 ms 468 KB Correct: 2988 out of 12000 queries used.
20 Correct 17 ms 548 KB Correct: 2979 out of 12000 queries used.
21 Correct 17 ms 592 KB Correct: 2985 out of 25000 queries used.
22 Correct 19 ms 568 KB Correct: 2995 out of 25000 queries used.
23 Correct 18 ms 560 KB Correct: 2976 out of 25000 queries used.
24 Correct 17 ms 564 KB Correct: 2973 out of 25000 queries used.
25 Correct 15 ms 468 KB Correct: 5310 out of 25000 queries used.
26 Correct 15 ms 540 KB Correct: 5191 out of 25000 queries used.
27 Correct 15 ms 468 KB Correct: 5142 out of 25000 queries used.
28 Correct 15 ms 528 KB Correct: 5414 out of 25000 queries used.
29 Correct 14 ms 448 KB Correct: 5393 out of 25000 queries used.
30 Correct 15 ms 468 KB Correct: 5386 out of 25000 queries used.
31 Correct 15 ms 536 KB Correct: 6164 out of 25000 queries used.
32 Correct 18 ms 596 KB Correct: 2982 out of 25000 queries used.
33 Correct 15 ms 472 KB Correct: 6086 out of 25000 queries used.
34 Correct 16 ms 468 KB Correct: 6156 out of 25000 queries used.
35 Correct 15 ms 524 KB Correct: 6093 out of 25000 queries used.
36 Correct 14 ms 468 KB Correct: 6156 out of 25000 queries used.
37 Correct 14 ms 528 KB Correct: 6142 out of 25000 queries used.
38 Correct 16 ms 536 KB Correct: 6161 out of 25000 queries used.
39 Correct 14 ms 536 KB Correct: 6106 out of 25000 queries used.
40 Correct 16 ms 468 KB Correct: 6196 out of 25000 queries used.
41 Correct 15 ms 468 KB Correct: 6135 out of 25000 queries used.
42 Correct 16 ms 468 KB Correct: 6141 out of 25000 queries used.
43 Correct 18 ms 592 KB Correct: 2991 out of 25000 queries used.
44 Correct 15 ms 532 KB Correct: 6079 out of 25000 queries used.
45 Correct 15 ms 528 KB Correct: 6100 out of 25000 queries used.
46 Correct 14 ms 468 KB Correct: 6057 out of 25000 queries used.
47 Correct 16 ms 520 KB Correct: 6148 out of 25000 queries used.
48 Correct 15 ms 468 KB Correct: 6119 out of 25000 queries used.
49 Correct 16 ms 468 KB Correct: 6108 out of 25000 queries used.
50 Correct 15 ms 524 KB Correct: 6126 out of 25000 queries used.
51 Correct 14 ms 536 KB Correct: 6119 out of 25000 queries used.
52 Correct 15 ms 472 KB Correct: 6136 out of 25000 queries used.
53 Correct 15 ms 468 KB Correct: 6136 out of 25000 queries used.
54 Correct 17 ms 568 KB Correct: 2997 out of 25000 queries used.
55 Correct 14 ms 596 KB Correct: 6105 out of 25000 queries used.
56 Correct 15 ms 476 KB Correct: 6108 out of 25000 queries used.
57 Correct 16 ms 648 KB Correct: 6154 out of 25000 queries used.
58 Correct 14 ms 536 KB Correct: 6109 out of 25000 queries used.
59 Correct 15 ms 468 KB Correct: 6123 out of 25000 queries used.
60 Correct 16 ms 552 KB Correct: 3891 out of 25000 queries used.
61 Correct 16 ms 548 KB Correct: 3972 out of 25000 queries used.
62 Correct 15 ms 468 KB Correct: 3967 out of 25000 queries used.
63 Correct 17 ms 468 KB Correct: 3887 out of 25000 queries used.
64 Correct 17 ms 616 KB Correct: 3922 out of 25000 queries used.
65 Correct 17 ms 560 KB Correct: 2970 out of 25000 queries used.
66 Correct 17 ms 540 KB Correct: 3930 out of 25000 queries used.
67 Correct 18 ms 468 KB Correct: 2977 out of 25000 queries used.
68 Correct 17 ms 556 KB Correct: 2973 out of 25000 queries used.
69 Correct 18 ms 596 KB Correct: 2989 out of 25000 queries used.
70 Correct 17 ms 572 KB Correct: 2979 out of 25000 queries used.