oj.uz

Submission #254252

# Submission time Handle Problem Language Result Execution time Memory
254252 2020-07-29T15:39:32 Z Saboon Homecoming (BOI18_homecoming) C++14
31 / 100
 312 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 = 6e7 + 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 29 ms 3320 KB Output is correct
8 Correct 12 ms 1408 KB Output is correct
9 Correct 24 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 199 ms 115832 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Runtime error 312 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 29 ms 3320 KB Output is correct
8 Correct 12 ms 1408 KB Output is correct
9 Correct 24 ms 2432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 199 ms 115832 KB Output is correct
12 Correct 20 ms 768 KB Output is correct
13 Runtime error 312 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -