QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177405#4581. Energy Generationucup-team288#WA 1ms3512kbC++202.9kb2023-09-12 22:24:422023-09-12 22:24:43

Judging History

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

  • [2023-09-12 22:24:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3512kb
  • [2023-09-12 22:24:42]
  • 提交

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';
}


Details

Tip: Click on the bar to expand more detailed information

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'