Submission #939375

#TimeUsernameProblemLanguageResultExecution timeMemory
939375winter0101City Mapping (NOI18_citymapping)C++14
96.20 / 100
8 ms8580 KiB
#include<bits/stdc++.h> #include "citymapping.h" using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> vector<pii>aaa[1009]; mt19937_64 rng(101094); long long d[1009][1009]; long long ask(int x,int y){ if (d[x][y]!=-1)return d[x][y]; return d[x][y]=d[y][x]=get_distance(x,y); } bool add[1009]; vector<int>xd[1009]; void solve(vector<int>&tmp,int s,int t){ if (sz(tmp)<=1)return; for (auto v:tmp)add[v]=0; shuffle(all(tmp),rng); s=tmp[0]; sort(all(tmp),[&](int i,int j){ return ask(s,i)<ask(s,j); }); vector<int>maybet; for (auto v:tmp)if (ask(s,v)==ask(s,tmp.back()))maybet.pb(v); shuffle(all(maybet),rng); t=maybet.back(); vector<int>vertice; for (auto v:tmp){ if (ask(s,v)+ask(t,v)==ask(s,t)){ vertice.pb(v); add[v]=1; } } sort(all(vertice),[&](int i,int j){ return ask(s,i)<ask(s,j); }); auto add_edg=[&](int u,int v,int w){ aaa[u].pb({v,w}); aaa[v].pb({u,w}); d[u][v]=d[v][u]=w; return; }; for1(i,1,sz(vertice)-1){ add_edg(vertice[i],vertice[i-1],ask(vertice[i],s)-ask(vertice[i-1],s)); } for(auto v:tmp){ if (add[v])continue; for (auto u:vertice){ if (ask(s,v)-ask(s,u)==ask(t,v)-ask(t,u)&&ask(s,v)>ask(s,u)){ xd[u].pb(v); } } } for (auto u:vertice){ if (!xd[u].empty()){ sort(all(xd[u]),[&](int i,int j){ return ask(i,s)<ask(j,s); }); for (auto v:xd[u]){ d[u][v]=d[v][u]=ask(v,s)-ask(u,s); } if (u!=s&&u!=t){ int news=xd[u][0],newt=xd[u].back(); add_edg(u,xd[u][0],d[u][xd[u][0]]); for (auto v:xd[u]){ d[v][xd[u][0]]=d[xd[u][0]][v]=d[u][v]-d[u][xd[u][0]]; } vector<int>cop; cop.swap(xd[u]); solve(cop,newt,news); } else { vector<int>cop; int news=u,newt=xd[u].back(); cop.swap(xd[u]); cop.pb(u); solve(cop,newt,news); } } } } void find_roads(int N, int Q, int A[], int B[], int W[]) { for1(i,1,N){ for1(j,1,N){ d[i][j]=-1; } d[i][i]=0; } vector<int>tree; for1(i,1,N)tree.pb(i); int s=rng()%N+1,t; while (true){ t=rng()%N+1; if (s==t)continue; break; } solve(tree,s,t); int cnt=0; for1(i,1,N){ for (auto v:aaa[i]){ if (v.fi>i){ A[cnt]=v.fi,B[cnt]=i,W[cnt]=v.se; cnt++; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...