oj.uz

Submission #254256

# Submission time Handle Problem Language Result Execution time Memory
254256 2020-07-29T15:45:52 Z Saboon Homecoming (BOI18_homecoming) C++14
31 / 100
 314 ms 262148 KB 
#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 <= 50){
		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));
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 1 ms 512 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 14 ms 3328 KB Output is correct
7 Correct 28 ms 3328 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 27 ms 2552 KB Output is correct
10 Correct 3 ms 512 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 117112 KB Output is correct
2 Correct 28 ms 2432 KB Output is correct
3 Runtime error 314 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 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 2 ms 640 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 14 ms 3328 KB Output is correct
7 Correct 28 ms 3328 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 27 ms 2552 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 188 ms 117112 KB Output is correct
12 Correct 28 ms 2432 KB Output is correct
13 Runtime error 314 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -