oj.uz

Submission #254254

# Submission time Handle Problem Language Result Execution time Memory
254254 2020-07-29T15:45:04 Z Saboon Homecoming (BOI18_homecoming) C++14
31 / 100
 302 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 <= 10){
		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 384 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 0 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 384 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 0 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 13 ms 3328 KB Output is correct
7 Correct 26 ms 3200 KB Output is correct
8 Correct 13 ms 1408 KB Output is correct
9 Correct 27 ms 2432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 115884 KB Output is correct
2 Correct 19 ms 768 KB Output is correct
3 Runtime error 302 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 384 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 0 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 13 ms 3328 KB Output is correct
7 Correct 26 ms 3200 KB Output is correct
8 Correct 13 ms 1408 KB Output is correct
9 Correct 27 ms 2432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 189 ms 115884 KB Output is correct
12 Correct 19 ms 768 KB Output is correct
13 Runtime error 302 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -