「BZOJ3073」[Pa2011]Journeys

Description

Seter建造了一个很大的星球,他准备建造NN个国家和无数双向道路。NN个国家很快建造好了,用1N1\cdots N编号,但是他发现道路实在太多了,他要一条条建简直是不可能的!于是他以如下方式建造道路:(a,b),(c,d)(a,b),(c,d)表示,对于任意两个国家xx,yy,如果axb,cyda\leq x\leq b,c\leq y\leq d,那么在xyxy之间建造一条道路。Seter保证一条道路不会修建两次,也保证不会有一个国家与自己之间有道路。
Seter好不容易建好了所有道路,他现在在位于PP号的首都。Seter想知道PP号国家到任意一个国家最少需要经过几条道路。当然,Seter保证PP号国家能到任意一个国家。

注意:可能有重边

Input

第一行三个数N,M,PN,M,PN500000,M100000N\leq 500000,M\leq 100000
后M行,每行4个数ABCDA,B,C,D1ABN,1CDN1\leq A\leq B\leq N,1\leq C\leq D\leq N

Output

NN行,第ii行表示PP号国家到第ii个国家最少需要经过几条路。显然第PP行应该是00

Sample Input

1
2
3
4
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3

Sample Output

1
2
3
4
5
1
1
2
0
1

Solution

线段树优化建边。
原理就是建两棵树,一棵树是父亲连儿子,一个是儿子连父亲。
一个节点表示区间里的点的出度或者入度。每一次建边就是节点连边就行了。
注意编号和线段树节点编号的互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 700000*4, M = 710000*4;
int n, m, P;
int d[N];
bool vis[N];
priority_queue<pii,vector<pii>,greater<pii> >q;
struct Edge {
int u, v, nxt, w;
}e[M * 2 + N * 2];
int head[N * 4], en, pos[N];
void dijkstra() {
memset(d, 0x3f, sizeof d);
d[pos[P]] = 0;
q.push(mk(0, pos[P]));
while(!q.empty()) {
pii now = q.top(); q.pop();
int x = now.nd;
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(d[y] > d[x] + e[i].w) {
d[y] = d[x] + e[i].w;
q.push(mk(d[y], y));
}
}
}
}
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
int ra, rb, tot;
struct Tree {
int l, r;
}t[N * 4 ];
void build(int &o, int l, int r, bool c) {
o = ++tot;
if(l == r) {
if(!c) pos[l] = o;
return;
}
int mid = (l + r) >> 1;
if(l <= mid) {
build(t[o].l, l, mid, c);
if(c) addedge(o, t[o].l, 0);
else addedge(t[o].l, o, 0);
}
if(r > mid) {
build(t[o].r, mid + 1, r, c);
if(c) addedge(o, t[o].r, 0);
else addedge(t[o].r, o, 0);
}
}
void addlef(int o, int l, int r) {
if(l == r) {
addedge(o, pos[l], 0);
return;
}
int mid = (l + r) >> 1;
if(l <= mid) addlef(t[o].l, l, mid);
if(r > mid) addlef(t[o].r, mid + 1, r);
}
void ins(int o, int L, int R, int l, int r, int x, bool c) {
if(l <= L && r >= R) {
if(c) addedge(x, o, 0);
else addedge(o, x, 0);
return;
}
int mid = (L + R) >> 1;
if(l <= mid) ins(t[o].l, L, mid, l, r, x, c);
if(r > mid) ins(t[o].r, mid + 1, R, l, r, x, c);
}
void update(int A, int B, int C, int D) {
int p1 = ++tot, p2 = ++tot;
ins(ra, 1, n, A, B, p1, 0);
addedge(p1, p2, 1);
ins(rb, 1, n, C, D, p2, 1);
}
int main() {
n = read(), m = read(), P = read();
build(ra, 1, n, 0);
build(rb, 1, n, 1);
addlef(rb, 1, n);
for(int i = 1; i <= m; ++i) {
int A = read(), B = read(), C = read(), D = read();
update(A, B, C, D);
update(C, D, A, B);
}
dijkstra();
for(int i = 1; i <= n; ++i)
writeln(d[pos[i]]);
return 0;
}