oj.uz

Submission #425453

# Submission time Handle Problem Language Result Execution time Memory
425453 2021-06-13T04:00:16 Z errorgorn City Mapping (NOI18_citymapping) C++17
100 / 100
 10 ms 588 KB 
#include "citymapping.h"
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;

int n;
vector<int> children;
long long depth[1005];
int sz[1005];
vector<int> al[1005];

int heavy_child(int i){
    if (al[i].size()==1 || sz[al[i][0]]>=sz[al[i][1]]) return al[i][0];
    else return al[i][1];
}

int heavy(int i){
    if (al[i].empty()) return i;
    return heavy(heavy_child(i));
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    n=N;

    long long best=-1;
    int root;

    long long temp;
    for (int x=2;x<=n;x++){
        temp=get_distance(1,x);
        if (temp>best){
            best=temp;
            root=x;
        }
    }

    for (int x=1;x<=n;x++){
        if (x==root) continue;
        depth[x]=get_distance(root,x);
        children.push_back(x);
    }

    sort(children.begin(),children.end(),[](int i,int j){
         return depth[i]<depth[j];
    });

    sz[root]=1;

    int index=0;

    int curr,h;
    long long extra;
    for (auto &it:children){
        sz[it]=1;
        curr=root;
        sz[root]++;

        while (al[curr].size()){
            h=heavy(curr);
            extra=(depth[h]+depth[it]-2*depth[curr]-get_distance(h,it))/2;
            while (extra){
                extra-=depth[heavy_child(curr)]-depth[curr];
                curr=heavy_child(curr);
                sz[curr]++;
            }

            if (al[curr].size()<2) break;
            if (al[curr][0]==heavy_child(curr)) curr=al[curr][1];
            else curr=al[curr][0];

            sz[curr]++;
        }

        al[curr].push_back(it);
        A[index]=curr;
        B[index]=it;
        W[index]=depth[it]-depth[curr];
        //printf("%d %d %lld\n",curr,it,depth[it]-depth[curr]);
        index++;
    }
}

Compilation message

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:42:30: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |         depth[x]=get_distance(root,x);
      |                  ~~~~~~~~~~~~^~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Correct: 2993 out of 500000 queries used.
2 Correct 7 ms 460 KB Correct: 2996 out of 500000 queries used.
3 Correct 2 ms 460 KB Correct: 5132 out of 500000 queries used.
4 Correct 3 ms 460 KB Correct: 6244 out of 500000 queries used.
5 Correct 3 ms 460 KB Correct: 3858 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Correct: 2993 out of 500000 queries used.
2 Correct 7 ms 460 KB Correct: 2996 out of 500000 queries used.
3 Correct 2 ms 460 KB Correct: 5132 out of 500000 queries used.
4 Correct 3 ms 460 KB Correct: 6244 out of 500000 queries used.
5 Correct 3 ms 460 KB Correct: 3858 out of 500000 queries used.
6 Correct 10 ms 580 KB Correct: 2984 out of 500000 queries used.
7 Correct 8 ms 460 KB Correct: 2990 out of 500000 queries used.
8 Correct 3 ms 460 KB Correct: 5070 out of 500000 queries used.
9 Correct 2 ms 492 KB Correct: 5779 out of 500000 queries used.
10 Correct 3 ms 460 KB Correct: 3888 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 568 KB Correct: 2969 out of 12000 queries used.
2 Correct 9 ms 552 KB Correct: 2975 out of 12000 queries used.
3 Correct 10 ms 460 KB Correct: 2996 out of 12000 queries used.
4 Correct 9 ms 540 KB Correct: 2975 out of 12000 queries used.
5 Correct 9 ms 560 KB Correct: 2969 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 568 KB Correct: 2969 out of 12000 queries used.
2 Correct 9 ms 552 KB Correct: 2975 out of 12000 queries used.
3 Correct 10 ms 460 KB Correct: 2996 out of 12000 queries used.
4 Correct 9 ms 540 KB Correct: 2975 out of 12000 queries used.
5 Correct 9 ms 560 KB Correct: 2969 out of 12000 queries used.
6 Correct 10 ms 492 KB Correct: 2990 out of 12000 queries used.
7 Correct 10 ms 460 KB Correct: 2984 out of 12000 queries used.
8 Correct 10 ms 588 KB Correct: 2996 out of 12000 queries used.
9 Correct 9 ms 588 KB Correct: 2987 out of 12000 queries used.
10 Correct 10 ms 460 KB Correct: 2978 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Correct: 2993 out of 500000 queries used.
2 Correct 7 ms 460 KB Correct: 2996 out of 500000 queries used.
3 Correct 2 ms 460 KB Correct: 5132 out of 500000 queries used.
4 Correct 3 ms 460 KB Correct: 6244 out of 500000 queries used.
5 Correct 3 ms 460 KB Correct: 3858 out of 500000 queries used.
6 Correct 10 ms 580 KB Correct: 2984 out of 500000 queries used.
7 Correct 8 ms 460 KB Correct: 2990 out of 500000 queries used.
8 Correct 3 ms 460 KB Correct: 5070 out of 500000 queries used.
9 Correct 2 ms 492 KB Correct: 5779 out of 500000 queries used.
10 Correct 3 ms 460 KB Correct: 3888 out of 500000 queries used.
11 Correct 10 ms 568 KB Correct: 2969 out of 12000 queries used.
12 Correct 9 ms 552 KB Correct: 2975 out of 12000 queries used.
13 Correct 10 ms 460 KB Correct: 2996 out of 12000 queries used.
14 Correct 9 ms 540 KB Correct: 2975 out of 12000 queries used.
15 Correct 9 ms 560 KB Correct: 2969 out of 12000 queries used.
16 Correct 10 ms 492 KB Correct: 2990 out of 12000 queries used.
17 Correct 10 ms 460 KB Correct: 2984 out of 12000 queries used.
18 Correct 10 ms 588 KB Correct: 2996 out of 12000 queries used.
19 Correct 9 ms 588 KB Correct: 2987 out of 12000 queries used.
20 Correct 10 ms 460 KB Correct: 2978 out of 12000 queries used.
21 Correct 9 ms 532 KB Correct: 2984 out of 25000 queries used.
22 Correct 8 ms 460 KB Correct: 2993 out of 25000 queries used.
23 Correct 8 ms 512 KB Correct: 2975 out of 25000 queries used.
24 Correct 8 ms 460 KB Correct: 2972 out of 25000 queries used.
25 Correct 3 ms 460 KB Correct: 4976 out of 25000 queries used.
26 Correct 2 ms 460 KB Correct: 4879 out of 25000 queries used.
27 Correct 2 ms 412 KB Correct: 4838 out of 25000 queries used.
28 Correct 2 ms 460 KB Correct: 5105 out of 25000 queries used.
29 Correct 2 ms 460 KB Correct: 5083 out of 25000 queries used.
30 Correct 3 ms 460 KB Correct: 5094 out of 25000 queries used.
31 Correct 2 ms 460 KB Correct: 5831 out of 25000 queries used.
32 Correct 9 ms 460 KB Correct: 2981 out of 25000 queries used.
33 Correct 2 ms 460 KB Correct: 5778 out of 25000 queries used.
34 Correct 2 ms 460 KB Correct: 5844 out of 25000 queries used.
35 Correct 3 ms 460 KB Correct: 5789 out of 25000 queries used.
36 Correct 3 ms 440 KB Correct: 5830 out of 25000 queries used.
37 Correct 2 ms 460 KB Correct: 5837 out of 25000 queries used.
38 Correct 3 ms 460 KB Correct: 5864 out of 25000 queries used.
39 Correct 2 ms 460 KB Correct: 5797 out of 25000 queries used.
40 Correct 2 ms 460 KB Correct: 5878 out of 25000 queries used.
41 Correct 2 ms 460 KB Correct: 5831 out of 25000 queries used.
42 Correct 2 ms 460 KB Correct: 5837 out of 25000 queries used.
43 Correct 9 ms 588 KB Correct: 2990 out of 25000 queries used.
44 Correct 2 ms 460 KB Correct: 5777 out of 25000 queries used.
45 Correct 2 ms 504 KB Correct: 5794 out of 25000 queries used.
46 Correct 2 ms 460 KB Correct: 5757 out of 25000 queries used.
47 Correct 3 ms 484 KB Correct: 5831 out of 25000 queries used.
48 Correct 3 ms 520 KB Correct: 5808 out of 25000 queries used.
49 Correct 2 ms 460 KB Correct: 5810 out of 25000 queries used.
50 Correct 3 ms 460 KB Correct: 5809 out of 25000 queries used.
51 Correct 2 ms 488 KB Correct: 5801 out of 25000 queries used.
52 Correct 2 ms 460 KB Correct: 5863 out of 25000 queries used.
53 Correct 3 ms 460 KB Correct: 5821 out of 25000 queries used.
54 Correct 8 ms 460 KB Correct: 2996 out of 25000 queries used.
55 Correct 2 ms 460 KB Correct: 5772 out of 25000 queries used.
56 Correct 2 ms 496 KB Correct: 5817 out of 25000 queries used.
57 Correct 2 ms 460 KB Correct: 5835 out of 25000 queries used.
58 Correct 2 ms 460 KB Correct: 5810 out of 25000 queries used.
59 Correct 3 ms 460 KB Correct: 5796 out of 25000 queries used.
60 Correct 3 ms 460 KB Correct: 3859 out of 25000 queries used.
61 Correct 3 ms 460 KB Correct: 3935 out of 25000 queries used.
62 Correct 3 ms 488 KB Correct: 3932 out of 25000 queries used.
63 Correct 3 ms 460 KB Correct: 3848 out of 25000 queries used.
64 Correct 3 ms 540 KB Correct: 3889 out of 25000 queries used.
65 Correct 8 ms 460 KB Correct: 2969 out of 25000 queries used.
66 Correct 3 ms 460 KB Correct: 3903 out of 25000 queries used.
67 Correct 8 ms 524 KB Correct: 2975 out of 25000 queries used.
68 Correct 8 ms 460 KB Correct: 2972 out of 25000 queries used.
69 Correct 8 ms 460 KB Correct: 2987 out of 25000 queries used.
70 Correct 8 ms 460 KB Correct: 2978 out of 25000 queries used.