oj.uz

Submission #254220

# Submission time Handle Problem Language Result Execution time Memory
254220 2020-07-29T14:46:12 Z Saboon Homecoming (BOI18_homecoming) C++14
13 / 100
 1000 ms 262148 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 204 ms 5120 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 204 ms 5120 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Runtime error 203 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 90400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 204 ms 5120 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Runtime error 203 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -