BZOJ4383 Pustynia（线段树+拓扑排序）

时间：2023-03-09 15:02:23
BZOJ4383 Pustynia（线段树+拓扑排序）

　　线段树优化建图暴力拓扑排序即可。对于已确定的数，拓扑排序时dp，每个节点都尽量取最大值，如果仍与已确定值矛盾则无解。叶子连出的边表示大于号，其余边表示大于等于。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

#define inf 1000000000

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,s,m,a[N<<],b[N],c[N],p[N<<],id[N],pos[N<<],degree[N<<],q[N<<],t,root,cnt;

bool flag[N];

struct data{int to,nxt;

}edge[N<<];

struct data2{int l,r;

}tree[N<<];

void addedge(int x,int y){t++;degree[y]++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void build(int &k,int l,int r)

{

    k=++cnt;a[k]=inf;

    if (l==r) {id[l]=k,pos[k]=l;if (flag[l]) a[k]=c[l];return;}

    int mid=l+r>>;

    build(tree[k].l,l,mid);

    build(tree[k].r,mid+,r);

    addedge(k,tree[k].l),

    addedge(k,tree[k].r);

}

void add(int p,int k,int l,int r,int x,int y)

{

    if (l==x&&r==y) {addedge(p,k);return;}

    int mid=l+r>>;

    if (y<=mid) add(p,tree[k].l,l,mid,x,y);

    else if (x>mid) add(p,tree[k].r,mid+,r,x,y);

    else add(p,tree[k].l,l,mid,x,mid),add(p,tree[k].r,mid+,r,mid+,y);

}

bool topsort()

{

    int head=,tail=;for (int i=;i<=cnt;i++) if (!degree[i]) q[++tail]=i;

    while (head<tail)

    {

        int x=q[++head],y=a[x]-(pos[x]>);

        for (int i=p[x];i;i=edge[i].nxt)

        {

            degree[edge[i].to]--;

            if (flag[pos[edge[i].to]])

            {

                if (a[edge[i].to]>y) return cout<<"NIE"<<endl,;

            }

            else a[edge[i].to]=min(a[edge[i].to],y);

            if (!degree[edge[i].to]) q[++tail]=edge[i].to;

        }

    }

    if (tail<cnt) return cout<<"NIE"<<endl,;

    else return cout<<"TAK"<<endl,;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4383.in","r",stdin);

    freopen("bzoj4383.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),s=read(),m=read();

    for (int i=;i<=s;i++)

    {

        int x=read(),y=read();

        c[x]=y;flag[x]=;

    }

    build(root,,n);

    for (int i=;i<=m;i++)

    {

        int l=read(),r=read(),k=read();

        for (int j=;j<=k;j++) b[j]=read();

        b[]=l-,b[k+]=r+;

        cnt++;a[cnt]=inf;

        for (int j=;j<=k+;j++)

        if (b[j-]+<=b[j]-) add(cnt,root,,n,b[j-]+,b[j]-);

        for (int j=;j<=k;j++) addedge(id[b[j]],cnt);

    }

    if (topsort()) for (int i=;i<=n;i++) printf("%d ",a[id[i]]);

    return ;

}

相关文章