Submission #95561

#	Time	Username	Problem	Language	Result	Execution time	Memory
95561		oolimry	City Mapping (NOI18_citymapping)	C++14	100 / 100	85 ms	872 KiB

citymapping

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

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