QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#333636#4269. Rainy MarketsEric12300 28ms50640kbC++142.5kb2024-02-20 10:55:102024-02-20 10:55:11

Judging History

你现在查看的是最新测评结果

  • [2024-02-20 10:55:11]
  • 评测
  • 测评结果:0
  • 用时:28ms
  • 内存:50640kb
  • [2024-02-20 10:55:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e6 + 10, M = 4e6 + 10, inf = 1e9;
int n, m, B[N], P[N], U[N], tot = 1, head[N], dis[N], pre[N], inq[N];
int id[N][3];
struct Edge {int v, next, c, w;} e[M << 1];
void add(int u, int v, int c, int w) {e[++tot] = (Edge) {v, head[u], c, w}, head[u] = tot;}
void Add(int u, int v, int c, int w) {/*cout << u << ' ' << v << ' ' << c << ' ' << w << endl, */add(u, v, c, w), add(v, u, 0, -w);}

bool SPFA(int s, int t) {
	memset(dis, 0x3f3f3f3f, sizeof dis);
    memset(pre, 0, sizeof pre);
    memset(inq, 0, sizeof inq);
    queue <int> q;
    dis[s] = 0, q.push(s), inq[s] = 1;
    while(!q.empty()) {
        int u = q.front();
        inq[u] = 0, q.pop();
        for(int i = head[u]; i; i = e[i].next) {
            int v = e[i].v, c = e[i].c, w = e[i].w;
            if(c && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pre[v] = i;
                if(!inq[v]) q.push(v), inq[v] = 1;
            }
        }
    }
    return pre[t] > 0;
}

pair<int, int> EK(int s, int t) {
    int mxflow = 0, mncost = 0;
    while(SPFA(s, t)) {
        int bottleneck = inf;
        for(int i = pre[t]; i; i = pre[e[i ^ 1].v])
            bottleneck = min(bottleneck, e[i].c);
        mxflow += bottleneck;
        for(int i = pre[t]; i; i = pre[e[i ^ 1].v]) {
            e[i].c -= bottleneck;
            e[i ^ 1].c += bottleneck;
            mncost += e[i].w * bottleneck;
        }
    }
    return make_pair(mxflow, mncost);
}

signed main() {
//	freopen("test.in", "r", stdin);
	ios :: sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> B[i];
	for(int i = 1; i <= n - 1; i++) cin >> P[i];
	for(int i = 1; i <= n - 1; i++) cin >> U[i];
	int S = 2 * n + 1, T = 2 * n + 2;
	for(int i = 1; i <= n - 1; i++) {
		Add(i, i + n, inf, 0);
		id[i][0] = tot;
		Add(i, i + n + 1, inf, 0);
		id[i][2] = tot;
		Add(i, T, U[i], 1);
		id[i][1] = tot;
//		cout << U[i] << '\n';
	}
	for(int i = 1; i <= n - 1; i++) Add(S, i, P[i], 0);
	for(int i = 1; i <= n; i++) Add(i + n, T, B[i], 0);
//	cout << "------------------------------\n";
	pair<int, int> ans = EK(S, T);
	int sum = 0;
	for(int i = 1; i <= n; i++) sum += P[i];
//	cout << ans.first << ' ' << ans.second << endl;
	if(ans.first != sum) return cout << "NO\n", 0;
	cout << "YES\n" << ans.second << '\n';
	for(int i = 1; i <= n - 1; i++) {
		for(int j = 0; j < 3; j++) cout << e[id[i][j]].c << ' ';
		cout << '\n';
	}
	return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 5
Accepted
time: 24ms
memory: 50424kb

input:

3
10 15 10
20 20
0 0

output:

NO

result:

ok IMPOSSIBLE

Test #2:

score: 0
Accepted
time: 8ms
memory: 50500kb

input:

2
813741488 132495829
946237313
0

output:

YES
0
813741484 0 132495829 

result:

ok good plan

Test #3:

score: 0
Accepted
time: 8ms
memory: 50636kb

input:

2
175700937 435906025
546265275
0

output:

YES
0
110359250 0 435906025 

result:

ok good plan

Test #4:

score: -5
Time Limit Exceeded

input:

1000000
999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 999998 99999...

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #36:

score: 5
Accepted
time: 15ms
memory: 50484kb

input:

3
10 15 10
20 20
0 11

output:

YES
5
10 0 10 
5 5 10 

result:

ok good plan

Test #37:

score: 0
Accepted
time: 28ms
memory: 50484kb

input:

4
5 3 1 2
7 6 2
3 2 4

output:

YES
4
5 2 0 
3 2 1 
0 0 2 

result:

ok good plan

Test #38:

score: 0
Accepted
time: 16ms
memory: 50420kb

input:

2
25 58
103
25

output:

YES
20
25 20 58 

result:

ok good plan

Test #39:

score: 0
Accepted
time: 7ms
memory: 50640kb

input:

2
400 400
121
200

output:

YES
0
0 0 121 

result:

ok good plan

Test #40:

score: -5
Time Limit Exceeded

input:

2000
98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 9...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%