Submission #1236235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236235		MarwenElarbi	City Mapping (NOI18_citymapping)	C++20	57 / 100	9 ms	9284 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
const long long nax=1e18;
int a[1005],b[1005],w[1005];
long long dis[1005][1005];
int k=0;
long long ask(int i,int j){
    if(dis[i][j]==-1) dis[i][j]=dis[j][i]=get_distance(i,j);
    return dis[i][j];
}
int furthest(int x,vector<int> tab){
    pair<long long,int> ans={-1,-1};
    for(auto u : tab) 
        if(u!=x){
            ans=max(ans,{ask(x,u),u});
        }
    return ans.se;
}
int current;
bool compare(int x,int y){
    return dis[current][x]<dis[current][y];
}
void recursive(vector<int> tab){
    if(tab.size()<=1) return;
    int x=furthest(tab[uniform_int_distribution<int>(0,(int)tab.size()-1)(rng)],tab);
    int y=furthest(x,tab);
    furthest(y,tab);
    current=y;
    vector<int> cur;
    vector<int> cnt;
    for (auto u : tab)
    {
        if(dis[x][u]+dis[u][y]==dis[x][y]) cur.push_back(u);
        else cnt.push_back(u);
    }
    sort(cur.begin(),cur.end(),compare);
    for (int i = 1; i < cur.size(); ++i)
    {
        a[k]=cur[i-1];
        b[k]=cur[i];
        w[k]=dis[current][cur[i]]-dis[current][cur[i-1]];
        k++;
    }
    vector<int> arr[1005];
    for(auto u:cnt){
        int l=0;
        int r=cur.size()-1;
        while(r-l>1){
            int mid=(r+l)/2;
            if(ask(cur[mid],u)>ask(cur[mid+1],u)) l=mid;
            else r=mid;
        }
        arr[cur[r]].push_back(u);
    }
    for (int i = 0; i < 1005; ++i)
    {
        if(!arr[i].empty()){
            pair<long long,int> ans={nax,-1};
            for(auto u:arr[i]) ans=min(ans,{dis[i][u],u});
            a[k]=ans.se;
            b[k]=i;
            w[k]=ans.fi;
            k++;
            recursive(arr[i]);
        }
    }
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
    memset(dis,-1,sizeof dis);
    for (int i = 1; i <= N; ++i) dis[i][i]=0;
    vector<int> tab;
    for (int i = 1; i <= N; ++i) tab.push_back(i);
    recursive(tab);
    for (int i = 0; i < N-1; ++i)
    {
        A[i]=a[i];B[i]=b[i];W[i]=w[i];
    }
    return;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 0 / 43