BZOJ3073 Journeys
Description
Seterは大きな星を建て、Nカ国と無数の双方向道路を建設するつもりだ.Nの国はすぐに建てられました.N番号ですが、彼は道が多すぎることに気づきました.彼が1本建てるのは不可能です.そこで彼は以下のように道路を建設した:(a,b)、(c,d)は、任意の2つの国x,yに対して、a<=x<=b,c<=y<=dであれば、xyの間に道路を建設することを示す.Seterは1つの道路が2回も建設されないことを保証し、1つの国と自分の間に道路があることを保証します.Seterはやっとすべての道路を建てた.彼は今P号の首都にいる.SeterはP号の国からどの国まで少なくともいくつかの道を通る必要があることを知りたい.もちろん、SeterはP号の国がどの国にも行けることを保証します.注意:重いエッジがある可能性があります
Input
最初の行の3つの数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
Sample Output
1
1
2
0
1
セグメントツリー構築図は、最短ルートを最適化します.有向辺:2本の線分木*****にリンクして、はっきり言って、正確性は自分でyyします.https://blog.csdn.net/lvzelong2014/article/details/79153621無向図を逆にもう一度やる.
ちょっと焦ったのは、スペースの複雑さには及ばない...いつもmle
Seterは大きな星を建て、Nカ国と無数の双方向道路を建設するつもりだ.Nの国はすぐに建てられました.N番号ですが、彼は道が多すぎることに気づきました.彼が1本建てるのは不可能です.そこで彼は以下のように道路を建設した:(a,b)、(c,d)は、任意の2つの国x,yに対して、a<=x<=b,c<=y<=dであれば、xyの間に道路を建設することを示す.Seterは1つの道路が2回も建設されないことを保証し、1つの国と自分の間に道路があることを保証します.Seterはやっとすべての道路を建てた.彼は今P号の首都にいる.SeterはP号の国からどの国まで少なくともいくつかの道を通る必要があることを知りたい.もちろん、SeterはP号の国がどの国にも行けることを保証します.注意:重いエッジがある可能性があります
Input
最初の行の3つの数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
Sample Output
1
1
2
0
1
セグメントツリー構築図は、最短ルートを最適化します.有向辺:2本の線分木*****にリンクして、はっきり言って、正確性は自分でyyします.https://blog.csdn.net/lvzelong2014/article/details/79153621無向図を逆にもう一度やる.
ちょっと焦ったのは、スペースの複雑さには及ばない...いつもmle
#include
using namespace std;
const int Maxn=500005*log2(500005);
struct Edge{
int cnt,h[Maxn],w[Maxn],to[Maxn],next[Maxn];
inline void add(int x,int y,int z){
next[++cnt]=h[x];to[cnt]=y;w[cnt]=z;h[x]=cnt;
}
}e;
#define to e.to[p]
int n,m,s;
int cnt,p[2][Maxn];
struct SegMent{
struct tree{
int l,r,ls,rs;
}t[Maxn];int root[2];
inline void link(int x,int l,int r,int y,int v,int cmd){
if(t[x].l>r||t[x].r>1;
if(l==r)return p[cmd][mid]=x,void();
build(t[x].ls,l,mid,cmd),build(t[x].rs,mid+1,r,cmd);
if(cmd){
e.add(x,t[x].ls,0),e.add(x,t[x].rs,0);
}else {
e.add(t[x].ls,x,0),e.add(t[x].rs,x,0);
}
}
}seg;
struct Dijkstra{
struct HeapNode{
int x,dist;
bool operator A.dist;
}
};
int dist[Maxn];
bool vst[Maxn];
inline void dijkstra(){
priority_queueQ;
memset(vst,0,sizeof(vst));
// for(int i=1;i<=n;++i)dist[p[1][i]]=0x3f3f3f3f;
memset(dist,63,sizeof(dist));
Q.push((HeapNode){p[1][s],dist[p[1][s]]=0});
while(!Q.empty()){
HeapNode tp=Q.top();Q.pop();
if(vst[tp.x])continue;
vst[tp.x]=1;
for(int p=e.h[tp.x];p;p=e.next[p])if(dist[to]>dist[tp.x]+e.w[p]){
dist[to]=dist[tp.x]+e.w[p];
Q.push((HeapNode){to,dist[to]});
}
}
}
}dij;
int main(){
// cout<