文件详细信息

下载本文件

本文件的大小为 3104 字节。

#include<cstdio>
#include<cstring>
#include<queue>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	void getstr(char*str){
		char ch=gc();
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t'&&ch!=EOF)*(str++)=ch,ch=gc();
		*str='\0';
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt;
		if(a==0)pc('0');
		cnt=0;
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
	void putstr(const char*str){
		while(*str!='\0')pc(*(str++));
	}
}
using IO::read;
using IO::getstr;
using IO::write;
using IO::putstr;
inline int max(const int a,const int b){
	return a>b?a:b;
}
const int maxn=100005,maxm=200005,maxk=300005,maxnode=(maxn<<1)+maxm,maxedge=maxk*20,lim=1000000000;
int n,s,m,solid[maxnode],a[maxnode];
int head[maxnode],total,in_deg[maxnode];
struct Edge{
	int to,next,len;
}e[maxedge];
void add(int u,int v,int w){
	e[++total]=Edge{v,head[u],w};
	head[u]=total;
	in_deg[v]++;
}
struct Seg{
	int l,r;
}T[maxn<<1];
int rt,tot,id[maxn];
void build(int&u,int l,int r){
	u=++tot;
	if(l==r){
		id[l]=u;
		return;
	}
	int m=(l+r)>>1;
	build(T[u].l,l,m);
	add(T[u].l,u,0);
	build(T[u].r,m+1,r);
	add(T[u].r,u,0);
}
int ql,qr;
void modify(int u,int l,int r){
	if(ql<=l&&r<=qr){
		add(u,tot,0);
		return;
	}
	int m=(l+r)>>1;
	if(ql<=m)modify(T[u].l,l,m);
	if(qr>m)modify(T[u].r,m+1,r);
}
int l,r,k,x[maxk];
int q[maxnode],front=1,tail;
bool vis[maxnode];
bool toposort(){
	for(int i=1;i<=n;i++)
		if(!in_deg[id[i]])
			q[++tail]=id[i];
	while(front<=tail){
		int u=q[front++];
		vis[u]=true;
		if(a[u]==-1)a[u]=1;
		if(solid[u]!=-1){
			if(a[u]<=solid[u])a[u]=solid[u];
			else return false;
		}
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			a[v]=max(a[v],a[u]+e[i].len);
			if((--in_deg[v])==0)q[++tail]=v;
		}
	}
	return true;
}
int main(){
	read(n),read(s),read(m);
	build(rt,1,n);
	memset(a,-1,sizeof(a));
	memset(solid,-1,sizeof(solid));
	for(int i=1,p,d;i<=s;i++){
		read(p),read(d);
		solid[id[p]]=d;
	}
	while(m--){
		read(l),read(r),read(k);
		for(int i=1;i<=k;i++)read(x[i]);
		x[0]=l-1,x[k+1]=r+1;
		tot++;
		for(int i=0;i<=k;i++)
			if(x[i+1]-x[i]>1){
				ql=x[i]+1,qr=x[i+1]-1;
				modify(rt,1,n);
			}
		for(int i=1;i<=k;i++)add(tot,id[x[i]],1);
	}
	if(!toposort()){
		putstr("NIE\n");
		return 0;
	}
	for(int i=1;i<=tot;i++)
		if(!vis[i]||a[i]>lim){
			putstr("NIE\n");
			return 0;
		}
	putstr("TAK\n");
	for(int i=1;i<=n;i++)write(a[id[i]]),pc(i!=n?' ':'\n');
	return 0;
}