JZOJ 5177. 【NOIP2017提高组模拟6.28】TRAVEL

Description

Input

Output

Sample Input

4 4

1 2 1 10

2 4 3 5

1 3 1 5

2 4 2 7

Sample Output

6

2 3 4 5 6 7

Solution

• 这题一眼望去有些难，特别是超级大的“泡泡怪”数量令人无从下手。
• 不过只需稍微思考，就很容易发现其答案一定是连续的一段，因为通过的也是一段。
• 而且进一步思考可以发现左右端点也会与虫洞限制重合，不然就会有扩展的更优解。
• 于是考虑在 M 个虫洞中枚举其左右限制，共 O(M2) ，再 O(N) 扫一遍判断是否可行。
• 但这样总时间复杂度就达到了 O(N∗M2) ，无法通过本题。
• 所以我们可以先将那 M 个虫洞按 R （右端点）从小到大排一次序，二分查找即可。
• 这样的总时间复杂度就是 O(N∗MlogM) ，AC本题。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=N*;
struct data
{
    int x,y;
}a[N*],ans;
int n,m,tot;
int first[N],next[M],en[M],w1[M],w2[M];
bool pd;
bool bz[N];
inline int read()
{
    int X=,w=; char ch=;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<)+(X<<)+ch-'0',ch=getchar();
    return X*w;
}
inline void write(int x)
{
     if(x<) putchar('-'),x=-x;
     if(x>) write(x/);
     putchar(x%+'0');
}
inline bool cmp(data x,data y)
{
    return x.y<y.y;
}
inline void insert(int x,int y,int l,int r)
{
    next[++tot]=first[x];
    first[x]=tot;
    en[tot]=y;
    w1[tot]=l,w2[tot]=r;
}
inline void dfs(int x,int l,int r)
{
    if(pd) return;
    if(x==n)
    {
        ans.x=l,ans.y=r;
        pd=true;
        return;
    }
    for(int i=first[x];i;i=next[i])
        if(!bz[en[i]] && w1[i]<=l && r<=w2[i])
        {
            bz[en[i]]=true;
            dfs(en[i],l,r);
        }
}
int main()
{
    n=read(),m=read();
    for(int i=;i<=m;i++)
    {
        int x=read(),y=read(),l=read(),r=read();
        a[i].x=l,a[i].y=r;
        insert(x,y,l,r);
        insert(y,x,l,r);
    }
    sort(a+,a++m,cmp);
    for(int i=ans.x=;i<=m;i++)
    {
        int l=,r=m;
        while(l<=r)
        {
            int mid=(l+r)>>;
            if(a[i].x<=a[mid].y)
            {
                if(a[mid].y-a[i].x<ans.y-ans.x)
                {
                    l=mid+;
                    continue;
                }
                if(a[mid].y-a[i].x==ans.y-ans.x && a[i].x>=ans.x)
                {
                    l=mid+;
                    continue;
                }
                memset(bz,false,sizeof(bz));
                pd=false;
                dfs(bz[]=,a[i].x,a[mid].y);
                if(pd) l=mid+; else r=mid-;
            }else l=mid+;
        }
    }
    write(ans.y-ans.x+),putchar('\n');
    for(int i=ans.x;i<=ans.y;i++) write(i),putchar(' ');
    return ;
}