IOI Railway

我只是来贴代码的，题解什么的，去问大神吧【顺便推广uoj】

提交地址：http://uoj.ac/problem/29

#include
#include
#include
#include
#include
#include
#include
#include "rail.h"const int MAXN = 50006,MAXM = 10000005;int f0 = 0, f1 = 0;
int d0[MAXN] = {0},d1[MAXN] = {0};struct station
{int dis,num;station(int dis = 0,int num = 0):dis(dis),num(num){}}a[MAXN] ,b[MAXN] ;
int al ,bl ;
int *loc,*type;
int pos[MAXM] = {0};inline void update(int x){pos[loc[x]] = type[x];}bool cmp(const station &p,const station &q)
{return (p.disint rr = a[1].num;loc[rr] = loc[0] + a[1].dis;type[rr] = 2;update(rr);for(int i = 2; i <= al ; i++){int t = a[i].num , tmp = getDistance(t,rr);if(pos[loc[rr]-((d0[rr] + tmp - d0[t])>>1)] == 2){loc[t] = loc[rr] - tmp;type[t] = 1;}else{loc[rr=t] = loc[0] + a[i].dis;type[t] = 2;}update(t);}}
void solve_left()
{int ll = b[1].num;loc[ll] = loc[f1] - b[1].dis;type[ll] = 1;update(ll);for(int i = 2; i <= bl ; i++){int t = b[i].num, tmp = getDistance(ll,t);if(pos[loc[ll]+((d1[ll] + tmp - d1[t])>>1)] == 1){loc[t] = loc[ll] + tmp;type[t]= 2; }else{loc[ll=t] = loc[f1] - b[i].dis;type[t] = 1;}   update(t);  }   
}void findLocation(int n, int first, int array1[],int array2[])
{loc = array1, type = array2;f0 = 0; loc[f0] = first;type[f0] = 1; update(f0);if(n==1)return ;d0[0] = 0;for(int i = 1 ; i < n ; i++)d0[i] = getDistance(0,i);for(int i = 1 ; i < n ; i++)a[i] = station(d0[i], i);std::sort(a + 1,a + n,cmp);f1 = a[1].num;loc[f1] = loc[0] + a[1].dis;type[f1] = 2;update(f1);d1[0] = d0[f1];for(int i = 1 ; i < n ; i++)d1[i] = (i!=f1)?getDistance(f1,i):0;for(int i = 1; i < n ; i++)if(i != f1 && d1[i] < d1[0] && d0[i] == d0[f1] + d1[i]){loc[i] = loc[f1] - d1[i];type[i] = 1;update(i);     }al =0 ,bl = 0;for(int i = 1 ; i < n ; i++)if(type[i] == 0)if(d0[i] != d0[f1] + d1[i]) a[++al] = station(d0[i],i);else              b[++bl] = station(d1[i],i);   if(al) {std::sort(a+1, a+al+1, cmp);solve_right();}if(bl) {std::sort(b+1, b+bl+1, cmp);solve_left();}return;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！