QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#333636 | #4269. Rainy Markets | Eric1230 | 0 | 28ms | 50640kb | C++14 | 2.5kb | 2024-02-20 10:55:10 | 2024-02-20 10:55:11 |
Judging History
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%