题解 P3588 【[POI2015]PUS】

2019-10-01 21:15:41


今天我才算是真正意义上理解了线段树优化建图

以前我只会一个点想一段区间连边

还不会许多点想许多区间连边

(其实本质意义上是一样的啊。。。)

唯一一个不同的就是要不要新开一个节点

连接两部分罢了

最后拓扑DP判断有无解

看是否有环是否满足范围即可

(其实最后要判a[i]是不是有小于0的

    如果有小于0的

    那就是无解

    但是我没判也A掉了

    懒得改了

放代码(其实我的代码很亲民的。。。)

#include<bits/stdc++.h>

using namespace std;

#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
    return x*f;
}

const int maxn=2e5+5;

int n,s,m,a[maxn<<3],head[maxn<<3],ver[maxn<<3],in[maxn<<3],len;
int nxt[maxn<<3],cnt,tot,bel[maxn<<3],pos[maxn<<3],xue[maxn<<3];

inline void add(int x,int y){
    nxt[++cnt]=head[x];
    head[x]=cnt;
    ver[cnt]=y;
}

inline void build(int k,int l,int r){
    if(l==r){
        bel[k]=l;
        pos[l]=k;
        return;
    }
    tot=max(tot,k<<1|1);
    add(k,k<<1);
    in[k<<1]++;
    add(k,k<<1|1);
    in[k<<1|1]++;
    build(lson);
    build(rson);
}

inline void connect(int k,int l,int r,int L,int R,int pos){
    if(L>R) return ;
    if(L<=l&&r<=R){
        add(pos,k);
        in[k]++;
        return ;
    }
    if(L<=mid) connect(lson,L,R,pos);
    if(R>mid) connect(rson,L,R,pos);
    return;
}

inline void topsort(){
    queue<int> q;
    q.push(1);
    a[1]=1e9;
    memset(xue,127,sizeof(xue));
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(bel[y]) xue[y]=min(xue[y],a[x]-1);
            else xue[y]=min(xue[y],a[x]);
            if(xue[y]<a[y]){
                cout<<"NIE\n";
                exit(0);
            }
            in[y]--;
            if(in[y]==0){
                if(bel[y]) len++;
                q.push(y);
                if(a[y]==0) a[y]=xue[y];
            }
        }
    }
}

int main(){
    n=read();s=read();m=read();
    build(1,1,n);
    for(int i=1;i<=s;i++){
        int x=read(),y=read();
        a[pos[x]]=y;
    }
//  for(int i=1;i<=n;i++) cout<<pos[i]<<" ";
//  cout<<endl<<endl;
//  for(int i=1;i<=n;i++) cout<<a[pos[i]]<<" ";
//  cout<<endl<<endl; 
    for(int i=1;i<=m;i++){
        int l=read(),r=read(),k=read();
        int last=l;
        int node_cnt=++tot;
        while(k--){
            int x=read();
//          cout<<pos[x]<<" "<<node_cnt<<endl;
            add(pos[x],node_cnt);
            in[node_cnt]++;
//          cout<<last<<" "<<x-1<<" "<<node_cnt<<endl; 
            connect(1,1,n,last,x-1,node_cnt);
            last=x+1;           
        }
//      cout<<last<<" "<<r<<" "<<node_cnt<<endl;
        connect(1,1,n,last,r,node_cnt);
//      cout<<endl;
    }
    topsort();
    if(len!=n){
        cout<<"NIE\n";
        return 0;
    }
    cout<<"TAK\n";
    for(int i=1;i<=n;i++) cout<<a[pos[i]]<<" ";
    cout<<endl;
    return 0;
}