【BZOJ 4383】[POI2015] Pustynia

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4383
数据传送门:http://oi.cyo.ng/?attachment_id=1911

题解

这个题暴力差分肯定可以做,就是边太多会爆炸
于是我们考虑先建一个像线段树一样的图
于是原题可以拆成6e5个区间连边
每一个区间又可以拆成log(n)个线段树上的点
于是复杂度就对辣!

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000000;
const int M = 5000000;
const int INF = 1000000000;

int head[N],to[M],nxt[M],cost[M],val[N],arr[N];
int sol[N],vis[N],in[N],n,m,s,bas,tot;
queue<pair<int,int> > leaf;

inline void Add_Edge(int u, int v, int w) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; 
	head[u] = T; cost[T] = w;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void build(int w, int l, int r) {
	bas = max(bas, w);
	if (l < r) {
		int mid = l + r + 1 >> 1;
		Add_Edge(w, w<<1, 0); build(w<<1, l, mid - 1);
		Add_Edge(w, w*2+1, 0); build(w*2+1, mid, r);
	} else {
		leaf.push(make_pair(w,l));
	}
}

bool Get_Ans(int w) {
	sol[w] = true;
	for (int i=head[w];i;i=nxt[i]) {
		if (vis[to[i]] && val[w] - cost[i] < val[to[i]]) {
			return false;
		} else {
			val[to[i]] = min(val[to[i]], val[w] - cost[i]);
			if (--in[to[i]] == 0) {
				if (!Get_Ans(to[i])) {
					return false;
				};
			}
		}
	}
	return true;
}

inline bool solve() {
	for (int i=1;i<=tot;i++) {
		if (!sol[i] && !in[i]) {
			if (!Get_Ans(i)) {
				return false;
			}
		}
	}
	return true;
} 

void insert(int w, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		Add_Edge(tot, w, 0);
	} else {
		int mid = l + r + 1 >> 1;
		if (L < mid) insert(w<<1, l, mid-1, L, R);
		if (R >= mid) insert(w*2+1, mid, r, L, R);
	}
}

int main(){
	n = read(); s = read(); m = read();
	build(1,1,n);
	while (!leaf.empty()) { 
		Add_Edge(leaf.front().first, leaf.front().second + bas, 0);
		leaf.pop(); 
	}
	tot = bas + n;
	fill(val, val+N, INF);
	for (int i=1,p;i<=s;i++) {
		p = read();
		val[p+bas] = read();
		vis[p+bas] = 1;
	}
		
	for (int i=1,l,r,k,last;i<=m;i++) {
		l = read(); r = read(); 
		k = read(); ++tot;
		for (int j=1,tmp;j<=k;j++) {
			arr[j] = tmp = read();
			Add_Edge(bas+tmp, tot, 1);
		}
		arr[0] = l-1; arr[k+1] = r+1;
		for (int j=1;j<=k+1;j++) {
			if (arr[j] - arr[j-1] > 1) {
				insert(1,1,n,arr[j-1]+1,arr[j]-1);
			} 
		}
	}
	if (!solve()) {
		puts("NIE");
	} else {
		for (int i=bas;i<=tot;i++) {
			if (in[i] || val[i] < 1) {
				puts("NIE");
				exit(0);
			}
		}
		
		puts("TAK");
		for (int i=1;i<=n;i++) 
			printf("%d ",val[i+bas]);
	}
	return 0;
}