3073: [Pa2011]Journeys
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 32 Solved: 17
[Submit][Status][Discuss]
Description
Seter建造了一个很大的星球，他准备建造N个国家和无数双向道路。N个国家很快建造好了，用1..N编号，但是他发现道路实在太多了，他要一条条建简直是不可能的！于是他以如下方式建造道路：(a,b),(c,d)表示，对于任意两个国家x,y，如果a<=x<=b,c<=y<=d，那么在xy之间建造一条道路。Seter保证一条道路不会修建两次，也保证不会有一个国家与自己之间有道路。
Seter好不容易建好了所有道路，他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然，Seter保证P号国家能到任意一个国家。
注意：可能有重边
Input
第一行三个数N,M,P。N<=500000,M<=100000。
后M行，每行4个数A，B，C，D。1<=A<=B<=N,1<=C<=D<=N。
Output
N行，第i行表示P号国家到第i个国家最少需要经过几条路。显然第P行应该是0。
Sample Input
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3
1 2 4 5
5 5 4 4
1 1 3 3
Sample Output
1
1
2
0
1
1
2
0
1
HINT
Source
RZZ的模拟赛里的一道题、、、比赛的时候直接放弃了满分写了个暴力上去。。。然后就连一等线都没有到。。。
标算是在线段树上挂链。。将每一条边在线段树上的区间找出来然后连边。。
用bfs求最短路。。对于一个点将覆盖他的区间提取出来，扩展他连向的区间。。用并查集维护一个点是否已经被bfs过。。
刚开始写了没有路径压缩的并查集。。然后很愉快的T了。。。真不知道当时是怎么想的。。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=500010;
struct data{int x,y1,y2,next,pre;} e[N<<3];
struct Tree{int l,r;} tree[N<<2];
int head[N<<2],a,b,c,d,n,m,p,f[N],dis[N],cnt,vis[N<<2],now,V[N];
queue <int> q;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int x,int y1,int y2){
e[++cnt].x = x;e[cnt].y1 = y1;e[cnt].y2 = y2;
e[cnt].next = head[x];head[x] = cnt;
}
void Build(int pos,int l,int r){
tree[pos].l = l;tree[pos].r = r;
if (l==r) return;
int mid = (l+r)>>1;
Build(pos<<1,l,mid);
Build(pos<<1|1,mid+1,r);
}
void Add(int pos,int l,int r,int valx,int valy){
if (tree[pos].l==l && tree[pos].r==r){Insert(pos,valx,valy);return;}
int mid = (tree[pos].l+tree[pos].r)>>1;
if (r<=mid) Add(pos<<1,l,r,valx,valy);
else if (l>mid) Add(pos<<1|1,l,r,valx,valy);
else Add(pos<<1,l,mid,valx,valy),Add(pos<<1|1,mid+1,r,valx,valy);
}
int get(int x){return f[x]==x?x:f[x] = get(f[x]);}
void find(int x){
int pos = 1;
for (;;){
if (!vis[pos]){
vis[pos] = 1;
for (int i=head[pos];i;i=e[i].next){
int t=get(e[i].y1);
while (t<=e[i].y2 && t!=0){
V[t] = 1;
dis[t] = dis[now]+1;
q.push(t);f[t] = t+1;
t = get(f[t]);
}
}
}
if (tree[pos].l==tree[pos].r) return;
int mid = (tree[pos].l+tree[pos].r)>>1;
if (x<=mid) pos = pos<<1;
else pos = pos<<1|1;
}
}
int main(){
n = read();m = read();p = read();
Build(1,1,n);
for (int i=1;i<=m;i++){
a = read();b = read();c = read();d = read();
Add(1,a,b,c,d);Add(1,c,d,a,b);
}
for (int i=1;i<=n;i++) f[i] = i;
q.push(p);f[p] = p+1;dis[p] = 0;V[p] = 1;
while (!q.empty()){now = q.front();q.pop();find(now);}
for (int i=1;i<=n;i++) printf("%d\n",dis[i]);
}
评论 (0)
