QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168694#5458. Shortest Path Querymendicillin2WA 56ms9540kbC++172.8kb2023-09-08 19:43:532023-09-08 19:43:54

Judging History

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

  • [2024-06-21 12:38:16]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:50ms
  • 内存:9440kb
  • [2023-09-08 19:43:54]
  • 评测
  • 测评结果:0
  • 用时:56ms
  • 内存:9540kb
  • [2023-09-08 19:43:53]
  • 提交

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 = ll;
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 = 1e18;

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<ll> 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 (ll v : ans) {
		cout << v << '\n';
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3820kb

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: 56ms
memory: 9540kb

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: 50ms
memory: 9512kb

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
200133621
10113118
271087083
209267636
201779806
240287544
184437502
286355239
230224204
199872977
204431768
234627085
213726953
74473192
246491918
56554467
300648338
109961816
92775038
369780497
211796173
255927507
146634720
60151714
128529157
114497756
172358378
208481871
498293...

result:

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