Submission #254258

#	Time	Username	Problem	Language	Result	Execution time	Memory
254258		Saboon	Homecoming (BOI18_homecoming)	C++14	Compilation error	0 ms	0 KiB

homecoming

#include<bits/stdc++.h>
#include"homecoming.h"
using namespace std;
typedef long long ll;
const int maxn = 6e6 + 20;
const int maxm = 7e7 + 20;
const ll inf = 1e18 + 7;

ll cap[maxm];
int cnt = 0, to[maxm], last[maxn], pre[maxm], pos[maxn];
void add_edge(int v, int u, ll c){
	to[cnt] = u, cap[cnt] = c, pre[cnt] = last[v], last[v] = cnt ++;
	to[cnt] = v, cap[cnt] = 0, pre[cnt] = last[u], last[u] = cnt ++;
}

int dis[maxn];

ll dfs(int source, int sink, ll untilnow){
	if (source == sink)
		return untilnow;
	ll now = 0;
	for (int &ed = pos[source]; ed != -1; ed = pre[ed]){
		if (cap[ed] and dis[to[ed]] == dis[source]+1){
			ll cur = dfs(to[ed], sink, min(cap[ed], untilnow));
			cap[ed] -= cur, cap[ed^1] += cur, now += cur, untilnow -= cur;
			if (untilnow == 0)
				return now;
		}
	}
	return now;
}

int Q[maxn], head = 0, tail = 0;

bool bfs(int n, int source, int sink){
	for (int i = 0; i < n; i++)
		dis[i] = -1;
	dis[source] = 0;
	tail = head = 0;
	Q[head++] = source;
	while (tail < head){
		int cur = Q[tail++];
		for (int ed = last[cur]; ed != -1; ed = pre[ed]){
			if (cap[ed] and dis[to[ed]] == -1){
				Q[head++] = to[ed];
				dis[to[ed]] = dis[cur]+1;
			}
		}
	}
	return dis[sink] != -1;
}

ll max_flow(int n, int src, int snk){
	ll maxFlow = 0;
	while (bfs(n, src, snk)){ 
		for (int i = 0; i < n; i++)
			pos[i] = last[i];
		maxFlow += dfs(src, snk, inf);
	}
	return maxFlow;
}

int lc[maxn], rc[maxn];
int newint;

void add(int id, int L, int R, int l, int r, int idx){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		add_edge(idx, id, inf);
		return;
	}
	int mid = (L + R) >> 1;
	add(lc[id], L, mid, l, r, idx);
	add(rc[id], mid, R, l, r, idx);
}

int N;

int build(int L, int R){
	if (L + 1 == R)
		return L+N;
	int me = newint ++;
	int mid = (L+R)>>1;
	lc[me] = build(L, mid);
	rc[me] = build(mid, R);
	add_edge(me, lc[me], inf);
	add_edge(me, rc[me], inf);
	return me;
}

ll solve(int n, int k, int* a, int* b){
	N = n;
	cnt = 0;
	int src = 2*n, snk = 2*n+1;
	for (int i = 0; i < 3*n+2; i++)
		last[i] = -1;
	newint = 2*n+2;
/*	if (k <= n and n <= 2000){
		for (int i = 0; i < n; i++)
			for (int j = i; j < i+k; j++)
				add_edge(i, n + j%n, inf);
	}
*/	else{
		int root = build(0, n);
		for (int i = 0; i < n; i++){
			int j = i + k;
			if (j < n)
				add(root, 0, n, i, j, i);
			else{
				add(root, 0, n, i, n, i);
				add(root, 0, n, 0, k-n+i, i);
			}
		}
	}
	for (int i = 0; i < n; i++){
		add_edge(src, i, a[i]);
		add_edge(n+i, snk, b[i]);
	}
	ll sum = 0;
	for (int i = 0; i < n; i++)
		sum += a[i];
	return max(0ll, sum - max_flow(newint, src, snk));
}

Compilation message (stderr)

homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:104:4: error: 'else' without a previous 'if'
 */ else{
    ^~~~