QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#333635#4269. Rainy MarketsEric12300 14ms60584kbC++142.5kb2024-02-20 10:52:262024-02-20 10:52:26

Judging History

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

  • [2024-02-20 10:52:26]
  • 评测
  • 测评结果:0
  • 用时:14ms
  • 内存:60584kb
  • [2024-02-20 10:52:26]
  • 提交

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][1] = tot;
		Add(i, T, U[i], 1);
		id[i][2] = 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
Wrong Answer

Test #1:

score: 5
Accepted
time: 12ms
memory: 60584kb

input:

3
10 15 10
20 20
0 0

output:

NO

result:

ok IMPOSSIBLE

Test #2:

score: -5
Wrong Answer
time: 3ms
memory: 58852kb

input:

2
813741488 132495829
946237313
0

output:

YES
0
813741484 132495829 0 

result:

wrong answer the number of umbrellas for sale at market 1 is 0, but you used 132495829 umbrella(s)

Subtask #2:

score: 0
Wrong Answer

Test #36:

score: 0
Wrong Answer
time: 14ms
memory: 60420kb

input:

3
10 15 10
20 20
0 11

output:

YES
5
10 10 0 
5 10 5 

result:

wrong answer the number of umbrellas for sale at market 1 is 0, but you used 10 umbrella(s)

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%