oj.uz

Submission #95561

# Submission time Handle Problem Language Result Execution time Memory
95561 2019-02-02T05:28:32 Z oolimry City Mapping (NOI18_citymapping) C++14
100 / 100
 85 ms 872 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> ii;
void find_roads(int n, int Q, int A[], int B[], int W[]) {
    //get_distance(-1,28798);
	ii arr[n];
	arr[0] = ii(0,0);
	for(int i = 1;i < n;i++){
        arr[i] = ii(get_distance(1,i+1),i);
	}

	sort(arr,arr+n);
	map<int,long long> m;
	for(int i = 0;i < n;i++){
        m[arr[i].second] = arr[i].first;
    }
	vector<int> child[n];
	int parent[n];
	int psize[n];
	fill(psize,psize+n,0);
	psize[0] = 1;
	parent[0] = -1;
    for(int i = 1;i < n;i++){
        int l = 0;
        int x = arr[i].second;
        set<int> s;
        int p = 0;
        while(true){
            p++;
            //if(p >= 2000) get_distance(-1,28798);
            s.insert(l);
            //printf("%d\n",l);
            if(child[l].size() == 0){
                long long xl = get_distance(x+1,l+1);
                long long d = (m[x] + m[l] - xl) / 2;
                int prel = l;
                //printf("%d %d %d\n",l,x,d);
                while(m[l] > d){

                    l = parent[l];
                    //if(l == -1)  get_distance(-1,28798);
                    //printf("%d\n",l);
                }
                //printf("%d ",d);
                if(l == prel){
                    //printf("%d %d\n",x,l);
                    A[i-1] = x+1;
                    B[i-1] = l+1;
                    W[i-1] = m[x] - m[l];
                    child[l].push_back(x);
                    parent[x] = l;
                    while(prel > 0){
                        psize[prel]++;
                        prel = parent[prel];
                    }
                    parent[0]++;
                    s.clear();
                    break;
                }
            }
            int maxi = -1;
            for(int j = 0;j < child[l].size();j++){
                if(s.find(child[l][j]) != s.end()) continue;
                if(maxi == -1 || psize[child[l][j]] > psize[maxi]){
                    maxi = child[l][j];
                }
            }
            if(maxi == -1){
                //printf("%d %d\n",x,l);
                A[i-1] = x+1;
                B[i-1] = l+1;
                W[i-1] = m[x] - m[l];
                child[l].push_back(x);
                parent[x] = l;
                int prel = l;
                while(prel > 0){
                    psize[prel]++;
                    prel = parent[prel];
                }
                parent[0]++;
                s.clear();
                break;
            }
            else{
                l = maxi;
            }
        }
    }

    //for(int i = 0;i < n-1;i++){
    //   printf("%d %d %d\n",A[i],B[i],W[i]);
    //}
	return;
}

Compilation message

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:63:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < child[l].size();j++){
                           ~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 632 KB Correct: 2692 out of 500000 queries used.
2 Correct 35 ms 632 KB Correct: 2422 out of 500000 queries used.
3 Correct 7 ms 504 KB Correct: 4518 out of 500000 queries used.
4 Correct 8 ms 632 KB Correct: 5568 out of 500000 queries used.
5 Correct 10 ms 616 KB Correct: 3388 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 632 KB Correct: 2692 out of 500000 queries used.
2 Correct 35 ms 632 KB Correct: 2422 out of 500000 queries used.
3 Correct 7 ms 504 KB Correct: 4518 out of 500000 queries used.
4 Correct 8 ms 632 KB Correct: 5568 out of 500000 queries used.
5 Correct 10 ms 616 KB Correct: 3388 out of 500000 queries used.
6 Correct 77 ms 688 KB Correct: 2010 out of 500000 queries used.
7 Correct 53 ms 632 KB Correct: 2064 out of 500000 queries used.
8 Correct 8 ms 632 KB Correct: 4245 out of 500000 queries used.
9 Correct 8 ms 504 KB Correct: 5090 out of 500000 queries used.
10 Correct 9 ms 632 KB Correct: 3055 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 628 KB Correct: 2087 out of 12000 queries used.
2 Correct 57 ms 632 KB Correct: 2305 out of 12000 queries used.
3 Correct 63 ms 632 KB Correct: 2458 out of 12000 queries used.
4 Correct 59 ms 632 KB Correct: 2471 out of 12000 queries used.
5 Correct 58 ms 632 KB Correct: 2241 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 628 KB Correct: 2087 out of 12000 queries used.
2 Correct 57 ms 632 KB Correct: 2305 out of 12000 queries used.
3 Correct 63 ms 632 KB Correct: 2458 out of 12000 queries used.
4 Correct 59 ms 632 KB Correct: 2471 out of 12000 queries used.
5 Correct 58 ms 632 KB Correct: 2241 out of 12000 queries used.
6 Correct 69 ms 692 KB Correct: 2474 out of 12000 queries used.
7 Correct 56 ms 688 KB Correct: 2383 out of 12000 queries used.
8 Correct 55 ms 632 KB Correct: 2208 out of 12000 queries used.
9 Correct 54 ms 760 KB Correct: 2236 out of 12000 queries used.
10 Correct 52 ms 636 KB Correct: 2303 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 632 KB Correct: 2692 out of 500000 queries used.
2 Correct 35 ms 632 KB Correct: 2422 out of 500000 queries used.
3 Correct 7 ms 504 KB Correct: 4518 out of 500000 queries used.
4 Correct 8 ms 632 KB Correct: 5568 out of 500000 queries used.
5 Correct 10 ms 616 KB Correct: 3388 out of 500000 queries used.
6 Correct 77 ms 688 KB Correct: 2010 out of 500000 queries used.
7 Correct 53 ms 632 KB Correct: 2064 out of 500000 queries used.
8 Correct 8 ms 632 KB Correct: 4245 out of 500000 queries used.
9 Correct 8 ms 504 KB Correct: 5090 out of 500000 queries used.
10 Correct 9 ms 632 KB Correct: 3055 out of 500000 queries used.
11 Correct 67 ms 628 KB Correct: 2087 out of 12000 queries used.
12 Correct 57 ms 632 KB Correct: 2305 out of 12000 queries used.
13 Correct 63 ms 632 KB Correct: 2458 out of 12000 queries used.
14 Correct 59 ms 632 KB Correct: 2471 out of 12000 queries used.
15 Correct 58 ms 632 KB Correct: 2241 out of 12000 queries used.
16 Correct 69 ms 692 KB Correct: 2474 out of 12000 queries used.
17 Correct 56 ms 688 KB Correct: 2383 out of 12000 queries used.
18 Correct 55 ms 632 KB Correct: 2208 out of 12000 queries used.
19 Correct 54 ms 760 KB Correct: 2236 out of 12000 queries used.
20 Correct 52 ms 636 KB Correct: 2303 out of 12000 queries used.
21 Correct 68 ms 632 KB Correct: 2503 out of 25000 queries used.
22 Correct 51 ms 632 KB Correct: 2072 out of 25000 queries used.
23 Correct 41 ms 632 KB Correct: 2285 out of 25000 queries used.
24 Correct 68 ms 632 KB Correct: 2037 out of 25000 queries used.
25 Correct 7 ms 504 KB Correct: 4437 out of 25000 queries used.
26 Correct 8 ms 632 KB Correct: 4359 out of 25000 queries used.
27 Correct 8 ms 632 KB Correct: 4308 out of 25000 queries used.
28 Correct 7 ms 504 KB Correct: 4418 out of 25000 queries used.
29 Correct 8 ms 632 KB Correct: 4503 out of 25000 queries used.
30 Correct 8 ms 632 KB Correct: 4443 out of 25000 queries used.
31 Correct 8 ms 508 KB Correct: 5152 out of 25000 queries used.
32 Correct 57 ms 684 KB Correct: 2224 out of 25000 queries used.
33 Correct 8 ms 504 KB Correct: 5084 out of 25000 queries used.
34 Correct 8 ms 504 KB Correct: 5159 out of 25000 queries used.
35 Correct 8 ms 504 KB Correct: 5101 out of 25000 queries used.
36 Correct 8 ms 632 KB Correct: 5119 out of 25000 queries used.
37 Correct 8 ms 504 KB Correct: 5145 out of 25000 queries used.
38 Correct 8 ms 504 KB Correct: 5103 out of 25000 queries used.
39 Correct 8 ms 612 KB Correct: 5136 out of 25000 queries used.
40 Correct 8 ms 504 KB Correct: 5169 out of 25000 queries used.
41 Correct 8 ms 504 KB Correct: 5125 out of 25000 queries used.
42 Correct 8 ms 628 KB Correct: 5204 out of 25000 queries used.
43 Correct 66 ms 872 KB Correct: 2088 out of 25000 queries used.
44 Correct 8 ms 504 KB Correct: 5117 out of 25000 queries used.
45 Correct 8 ms 632 KB Correct: 5091 out of 25000 queries used.
46 Correct 8 ms 504 KB Correct: 5069 out of 25000 queries used.
47 Correct 7 ms 632 KB Correct: 5180 out of 25000 queries used.
48 Correct 8 ms 632 KB Correct: 5136 out of 25000 queries used.
49 Correct 8 ms 632 KB Correct: 5092 out of 25000 queries used.
50 Correct 8 ms 504 KB Correct: 5106 out of 25000 queries used.
51 Correct 8 ms 632 KB Correct: 5100 out of 25000 queries used.
52 Correct 8 ms 632 KB Correct: 5129 out of 25000 queries used.
53 Correct 9 ms 632 KB Correct: 5145 out of 25000 queries used.
54 Correct 46 ms 632 KB Correct: 2334 out of 25000 queries used.
55 Correct 8 ms 632 KB Correct: 5197 out of 25000 queries used.
56 Correct 8 ms 652 KB Correct: 5142 out of 25000 queries used.
57 Correct 8 ms 632 KB Correct: 5126 out of 25000 queries used.
58 Correct 8 ms 504 KB Correct: 5116 out of 25000 queries used.
59 Correct 7 ms 632 KB Correct: 5105 out of 25000 queries used.
60 Correct 9 ms 632 KB Correct: 3042 out of 25000 queries used.
61 Correct 10 ms 632 KB Correct: 3318 out of 25000 queries used.
62 Correct 10 ms 632 KB Correct: 2918 out of 25000 queries used.
63 Correct 10 ms 632 KB Correct: 3318 out of 25000 queries used.
64 Correct 9 ms 632 KB Correct: 3104 out of 25000 queries used.
65 Correct 66 ms 632 KB Correct: 2068 out of 25000 queries used.
66 Correct 11 ms 632 KB Correct: 3229 out of 25000 queries used.
67 Correct 55 ms 636 KB Correct: 2019 out of 25000 queries used.
68 Correct 52 ms 632 KB Correct: 2395 out of 25000 queries used.
69 Correct 56 ms 632 KB Correct: 2452 out of 25000 queries used.
70 Correct 52 ms 724 KB Correct: 2415 out of 25000 queries used.