## 【BZOJ 4383】[POI2015] Pustynia

#### 代码

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

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

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;
}

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;
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) {
} 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(){
build(1,1,n);
while (!leaf.empty()) {
leaf.pop();
}
tot = bas + n;
fill(val, val+N, INF);
for (int i=1,p;i<=s;i++) {
vis[p+bas] = 1;
}

for (int i=1,l,r,k,last;i<=m;i++) {
for (int j=1,tmp;j<=k;j++) {
}
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;
}