제출 #939350

#제출 시각아이디문제언어결과실행 시간메모리
939350winter0101City Mapping (NOI18_citymapping)C++14
57.10 / 100
7 ms8792 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); vector<int>cc[1009]; int f[1009]; 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); } int fs(int u){ if (f[u]<0)return u; return f[u]=fs(f[u]); } void unite(int u,int v,int w){ int u1=u,v1=v; u=fs(u),v=fs(v); if (u==v)return; if (f[u]>f[v]){ swap(u,v); swap(u1,v1); } f[u]+=f[v]; for (auto vx:cc[u]){ for (auto vy:cc[v]){ d[vx][vy]=d[vy][vx]=1ll*w+d[vx][u1]+d[vy][v1]; } } for (auto vx:cc[v]){ cc[u].pb(vx); } cc[v].clear(); } 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; sort(all(tmp),[&](int i,int j){ return ask(s,i)<ask(s,j); }); t=tmp.back(); sort(all(tmp),[&](int i,int j){ return ask(t,i)<ask(t,j); }); if (ask(s,t)<ask(t,tmp.back()))s=tmp.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; unite(u,v,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){ f[i]=-1; cc[i].pb(i); 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...