Submission #254220

#	Time	Username	Problem	Language	Result	Execution time	Memory
254220		Saboon	Homecoming (BOI18_homecoming)	C++14	13 / 100	1092 ms	262148 KiB

homecoming

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

int cnt = 0, to[maxm], cap[maxm], last[maxn], pre[maxm], pos[maxn];
void add_edge(int v, int u, int 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];

int dfs(int source, int sink, int untilnow){
	if (source == sink)
		return untilnow;
	int now = 0;
	for (int &ed = pos[source]; ed != -1; ed = pre[ed]){
		if (cap[ed] and dis[to[ed]] == dis[source]+1){
			int 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 source, int sink){
	for (int i = 0; i <= sink; 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(src, snk)){ 
		for (int i = 0; i < n; i++)
			pos[i] = last[i];
		maxFlow += dfs(src, snk, inf);
	}
	return maxFlow;
}

ll solve(int n, int k, int* a, int* b){
	cnt = 0;
	int src = 2*n, snk = 2*n+1;
	for (int i = 0; i < 2*n+2; i++)
		last[i] = -1;
	for (int i = 0; i < n; i++)
		for (int j = i; j < i+k; j++)
			add_edge(i, n+j%n, inf);
	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(2*n+2, src, snk));
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38