codeforces gym100959 I - Robots（稠密图建图优化）

I - Robots

显然可以两点之间能连边就连边，但是边数会很多，考虑优化
对于三个点$(x_0,y_0)$，$(x_0,y_1)$，$(x_0,y_2)$

如果三个点的方向都是$U$ 那么没有必要$1\to 3$连边只需要让$2$作为中转站连边即$1\to 2\to 3$连边即可。

这样边数就是线性的。

upd：向上面建图不难发现每个点只会和启动它的点连一条边，因此边数是$O(n)$量级的

#include<bits/stdc++.h> using namespace std; constexpr int N=100010; struct node {int x,y;char d; }a[N]; int b[2*N],n,m; vector<pair<int,int> > gx[2*N]; vector<pair<int,int> > gy[2*N]; long long d[N]; long long T; bool vis[N]; void dijkstra() {priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;memset(d,0x3f,sizeof d);q.push({0,1});d[1]=0;while(q.size()){int u=q.top().second; q.pop();if(vis[u]) continue;vis[u]=1;if(a[u].d=='U'){vector<pair<int,int> >::iterator it=lower_bound(gx[a[u].x].begin(),gx[a[u].x].end(),(pair<int,int>){a[u].y,u});++it;while(it!=gx[a[u].x].end()){int v=it->second;if(d[v]>d[u]+b[a[v].y]-b[a[u].y]){d[v]=d[u]+b[a[v].y]-b[a[u].y];q.push({d[v],v});}if(a[v].d=='U') break;it++;}}if(a[u].d=='D'){vector<pair<int,int> >::iterator it=lower_bound(gx[a[u].x].begin(),gx[a[u].x].end(),(pair<int,int>){a[u].y,u});if(it==gx[a[u].x].begin()) continue;--it;while(1){int v=it->second;if(d[v]>d[u]-b[a[v].y]+b[a[u].y]){d[v]=d[u]-b[a[v].y]+b[a[u].y];q.push({d[v],v});}if(a[v].d=='D') break;if(it==gx[a[u].x].begin()) break;it--;}}if(a[u].d=='R'){vector<pair<int,int> >::iterator it=lower_bound(gy[a[u].y].begin(),gy[a[u].y].end(),(pair<int,int>){a[u].x,u});++it;while(it!=gy[a[u].y].end()){int v=it->second;if(d[v]>d[u]+b[a[v].x]-b[a[u].x]){d[v]=d[u]+b[a[v].x]-b[a[u].x];q.push({d[v],v});}if(a[v].d=='R') break;it++;}}if(a[u].d=='L'){vector<pair<int,int> >::iterator it=lower_bound(gy[a[u].y].begin(),gy[a[u].y].end(),(pair<int,int>){a[u].x,u});if(it==gy[a[u].y].begin()) continue;--it;while(1){int v=it->second;if(d[v]>d[u]-b[a[v].x]+b[a[u].x]){d[v]=d[u]-b[a[v].x]+b[a[u].x];q.push({d[v],v});}if(a[v].d=='L') break;if(it==gy[a[u].y].begin()) break;it--;}}} } int main() {cin>>n>>T;for(int i=1;i<=n;i++){int x,y;char d;cin>>x>>y>>d;a[i]={x,y,d};b[++m]=x;b[++m]=y;}sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;for(int i=1;i<=n;i++){a[i].x=lower_bound(b+1,b+1+m,a[i].x)-b;a[i].y=lower_bound(b+1,b+1+m,a[i].y)-b;}for(int i=1;i<=n;i++){gx[a[i].x].push_back({a[i].y,i});gy[a[i].y].push_back({a[i].x,i});}for(int i=1;i<=m;i++) {sort(gx[i].begin(),gx[i].end());sort(gy[i].begin(),gy[i].end());}dijkstra();for(int i=1;i<=n;i++){if(d[i]==0x3f3f3f3f3f3f3f3f||T<=d[i])cout<<b[a[i].x]<<' '<<b[a[i].y]<<'\n';else{long long x=b[a[i].x],y=b[a[i].y];if(a[i].d=='U') y+=T-d[i];if(a[i].d=='D') y-=T-d[i];if(a[i].d=='R') x+=T-d[i];if(a[i].d=='L') x-=T-d[i];cout<<x<<' '<<y<<'\n';}}return 0; }

想到做法了，但是以为可能还有数据能把边卡到2次方，就帮队友调题去了~~非常可惜

总结

以上是生活随笔为你收集整理的codeforces gym100959 I - Robots（稠密图建图优化）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。