链接
题目传送门: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; }