Submission #1236234

#TimeUsernameProblemLanguageResultExecution timeMemory
1236234MarwenElarbiCity Mapping (NOI18_citymapping)C++20
Compilation error
0 ms0 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; }

Compilation message (stderr)

citymapping.cpp:3:1: error: 'mt19937' does not name a type
    3 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      | ^~~~~~~
citymapping.cpp: In function 'void recursive(std::vector<int>)':
citymapping.cpp:29:75: error: 'rng' was not declared in this scope
   29 |     int x=furthest(tab[uniform_int_distribution<int>(0,(int)tab.size()-1)(rng)],tab);
      |                                                                           ^~~