oj.uz

Submission #254257

# Submission time Handle Problem Language Result Execution time Memory
254257 2020-07-29T15:46:43 Z Saboon Homecoming (BOI18_homecoming) C++14
31 / 100
 1000 ms 129656 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 <= n and n <= 2000){
		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 10 ms 6784 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 3 ms 2048 KB Output is correct
5 Correct 2 ms 1664 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 10 ms 6784 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 3 ms 2048 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 13 ms 3328 KB Output is correct
7 Correct 26 ms 3328 KB Output is correct
8 Correct 469 ms 78884 KB Output is correct
9 Correct 24 ms 2432 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 Execution timed out 1095 ms 129656 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 10 ms 6784 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 3 ms 2048 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 13 ms 3328 KB Output is correct
7 Correct 26 ms 3328 KB Output is correct
8 Correct 469 ms 78884 KB Output is correct
9 Correct 24 ms 2432 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Execution timed out 1095 ms 129656 KB Time limit exceeded
12 Halted 0 ms 0 KB -