Submission #425453

#	Time	Username	Problem	Language	Result	Execution time	Memory
425453		errorgorn	City Mapping (NOI18_citymapping)	C++17	100 / 100	10 ms	588 KiB

citymapping

#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 (stderr)

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 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43