QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177405 | #4581. Energy Generation | ucup-team288# | WA | 1ms | 3512kb | C++20 | 2.9kb | 2023-09-12 22:24:42 | 2023-09-12 22:24:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ll = long long;
#define pb emplace_back
#define X first
#define Y second
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true);}
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true);}
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l++ << " \n"[l==r]; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
template <typename F>
struct Flow {
static constexpr F INF = numeric_limits<F>::max() / 2;
struct Edge {
int to;
F cap;
Edge(int to, F cap) : to(to), cap(cap) {}
};
int n;
vector<Edge> e;
vector<vector<int>> adj;
vector<int> cur, h;
Flow(int n) : n(n), adj(n) {}
bool bfs(int s, int t) {
h.assign(n, -1);
queue<int> q;
h[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i : adj[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) { return true; }
q.push(v);
}
}
}
return false;
}
F dfs(int u, int t, F f) {
if (u == t) { return f; }
F r = f;
for (int &i = cur[u]; i < int(adj[u].size()); i++) {
int j = adj[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
F a = dfs(v, t, min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0) { return f; }
}
}
return f - r;
}
void addEdge(int u, int v, F cf = INF, F cb = 0) {
adj[u].push_back(e.size()), e.emplace_back(v, cf);
adj[v].push_back(e.size()), e.emplace_back(u, cb);
}
F maxFlow(int s, int t) {
F ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, INF);
}
return ans;
}
};
const int MAX_N = 300010;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, R, G, P;
cin >> n >> R >> G >> P;
G *= 2;
vector<int> x(n), y(n), d(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> d[i];
d[i] /= 90;
if (d[i] % 4 >= 2) {
d[i] ^= 1;
}
}
vector<pair<int, int>> pairs;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (x[i] != x[j] && y[i] != y[j] && (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= R * R) {
pairs.emplace_back(i, j);
}
}
}
int ans = G * int(pairs.size()) + P * n;
int S = 2 * n, T = S + 1;
for (int b = 0; b < 2; b++) {
Flow<int> mf(T + 1);
for (int i = 0; i < n; i++) {
int x = d[i] >> b & 1;
mf.addEdge(S, 2 * i, x == 0 ? 0 : P);
mf.addEdge(2 * i + 1, T, x == 1 ? 0 : P);
}
for (auto [u, v] : pairs) {
mf.addEdge(2 * u, 2 * v + 1, G);
mf.addEdge(2 * v, 2 * u + 1, G);
}
ans -= mf.maxFlow(S, T);
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3472kb
input:
3 10 10 15 0 0 0 2 2 180 100 100 180
output:
35
result:
ok single line: '35'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
3 10 1 1000 0 0 0 2 2 0 -4 4 180
output:
2998
result:
ok single line: '2998'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
4 10 1000 1 0 0 0 0 2 90 2 0 180 2 2 270
output:
4002
result:
ok single line: '4002'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
10 1000 1 2 186 98 180 206 689 270 695 90 90 292 247 90 -405 -125 270 928 -887 90 -45 -233 270 58 625 90 -215 136 270 -858 672 90
output:
62
result:
ok single line: '62'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3512kb
input:
50 322 127 256 -418 -408 0 -317 -390 90 -208 -295 270 -187 -379 90 -343 -395 0 -278 -279 270 -191 -239 270 -192 -411 180 -203 -181 90 -330 -231 0 387 -416 180 352 -402 270 138 -181 0 299 -435 180 261 -273 0 191 -433 270 430 -182 0 290 -375 90 293 -426 90 458 -297 270 -416 278 270 -411 167 90 -312 23...
output:
68092
result:
wrong answer 1st lines differ - expected: '66300', found: '68092'