| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1236234 | MarwenElarbi | City Mapping (NOI18_citymapping) | C++20 | 0 ms | 0 KiB |
#include "citymapping.h"
#include <bits/stdc++.h>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
#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;
}