QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168693#5458. Shortest Path Querymendicillin2WA 80ms9144kbC++172.8kb2023-09-08 19:43:012023-09-08 19:43:01

Judging History

你现在查看的是测评时间为 2023-09-08 19:43:01 的历史记录

  • [2024-06-21 12:38:15]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:65ms
  • 内存:9300kb
  • [2023-09-08 19:43:01]
  • 评测
  • 测评结果:0
  • 用时:80ms
  • 内存:9144kb
  • [2023-09-08 19:43:01]
  • 提交

answer

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

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

using D = int;
int sgn(D a) {
	return (a > 0) - (a < 0);
}

struct P {
	D x, y;
	P(D x_ = 0, D y_ = 0) : x(x_), y(y_) {}

	P operator + (const P& o) const { return P(x + o.x, y + o.y); }
	P operator - (const P& o) const { return P(x - o.x, y - o.y); }
};
D cross(const P& a, const P& b) {
	return a.x * b.y - a.y * b.x;
}
D cross(const P& a, const P& b, const P& c) {
	return cross(b - a, c - a);
}

vc<P> lower_hull(vc<P> pts) {
	int n = sz(pts);
	sort(pts.begin(), pts.end(), [&](const P& a, const P& b) -> bool {
		return tie(a.x, a.y) < tie(b.x, b.y);
	});
	vc<P> res;
	for (int i = 0; i < n; res.push_back(pts[i++])) {
		for (; res.size() > 1 && sgn(cross(res.end()[-2], res.end()[-1], pts[i])) <= 0; res.pop_back()) {}
	}
	return res;
}

#define LOCAL true

#if LOCAL
constexpr int L = 3;
#else
constexpr int L = 1010;
#endif

const ll INF = 1e9;

template <class T> void setmin(T& a, const T& b) {
	if (a > b) a = b;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int N, M; cin >> N >> M;
	struct edge_t {
		int b, c;
	};
	vector<edge_t> edges(M);
	vector<vector<int>> adj(N);
	for (int e = 0; e < M; e++) {
		int u, v, c; cin >> u >> v >> c; u--, v--;
		assert(u < v);
		edges[e] = {v, c};
		adj[u].push_back(e);
	}

	int Q; cin >> Q;
	struct query_t {
		int a, b;
	};
	vector<query_t> queries(Q);
	vector<vector<int>> queries_at(N);
	for (int q = 0; q < Q; q++) {
		int a, b, x; cin >> a >> b >> x; x--;
		queries[q] = {a, b};
		queries_at[x].push_back(q);
	}

	vector<int> ans(Q, INF);
	
	vector<vector<P>> dp(L);
	dp[0].emplace_back(0, 0);
	for (int x = 0; x < N; x++) {
		auto& cnds = dp[x % L];
		cnds = lower_hull(cnds);

		for (int q : queries_at[x]) {
			const auto& [a, b] = queries[q];
			for (const auto& pt : cnds) {
				setmin(ans[q], a * pt.x + b * pt.y);
			}
		}

		for (int e : adj[x]) {
			const auto& [y, c] = edges[e];
			const int dx = (c == 0 ? 1 : 0);
			const int dy = (c == 0 ? 0 : 1);
			auto& tgt = dp[y % L];
			for (const auto& pt : cnds) {
				tgt.emplace_back(pt.x + dx, pt.y + dy);
			}
		}

		cnds.clear();
	}

	for (int v : ans) {
		cout << v << '\n';
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3568kb

input:

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: 0
Accepted
time: 70ms
memory: 9112kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

164602050
208733870
228180204
248456409
87574800
16685198
46684062
64713954
46949896
240633535
94777502
83016099
259833741
167838804
214963500
147454419
111021650
80187604
184782450
78138570
86528820
203553394
188095596
202049239
290053220
172790198
168899028
97757186
96431009
266952297
164349486
26...

result:

ok 50000 numbers

Test #3:

score: -100
Wrong Answer
time: 80ms
memory: 9144kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 0
6 7 1
7 8 0
8 9 0
9 10 1
10 11 1
11 12 1
12 13 1
13 14 0
14 15 1
15 16 1
16 17 1
17 18 0
18 19 0
19 20 1
20 21 1
21 22 1
22 23 0
23 24 0
24 25 1
25 26 1
26 27 0
27 28 0
28 29 1
29 30 0
30 31 1
31 32 1
32 33 1
33 34 0
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

207236462
64935253
-2013314627
10113118
271087083
209267636
-2143426405
240287544
184437502
-2009848075
-1885814346
-216854452
204431768
234627085
-273364603
-1490026777
246491918
56554467
300648338
-1562891983
92775038
-362788086
211796173
-1939023004
-587123726
-932084455
128529157
-80697416
-1960...

result:

wrong answer 1st numbers differ - expected: '100196045', found: '207236462'