QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75483 | #5458. Shortest Path Query | skittles1412 | Compile Error | / | / | C++14 | 2.7kb | 2023-02-05 12:59:01 | 2024-06-21 12:37:03 |
Judging History
你现在查看的是最新测评结果
- [2024-06-21 12:37:03]
- 管理员手动重测本题所有提交记录
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-02-05 12:59:02]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-02-05 12:59:01]
- 提交
answer
#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
using C = complex<long>;
template <typename T>
int sign(T x) {
return (x > 0) - (x < 0);
}
// 1 if a is left of b
long oleft(C a, C b) {
return sign(imag(a * conj(b)));
}
vector<C> lower_convex_hull(vector<C> arr) {
sort(begin(arr), end(arr), [&](C a, C b) -> bool {
if (real(a) != real(b)) {
return real(a) < real(b);
}
return imag(a) > imag(b);
});
vector<C> ans;
for (auto& a : arr) {
while (sz(ans) >= 2) {
auto c = end(ans)[-2], b = end(ans)[-1];
if (oleft(b - c, a - b) >= 0) {
ans.pop_back();
} else {
break;
}
}
ans.push_back(a);
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, bool>> graph[n];
for (int i = 0; i < m; i++) {
int u, v;
bool w;
cin >> u >> v >> w;
u--;
v--;
graph[u].emplace_back(v, w);
}
int q;
cin >> q;
int qans[q];
vector<array<int, 3>> queries[n];
for (int i = 0; i < q; i++) {
int a, b, u;
cin >> a >> b >> u;
u--;
queries[u].push_back({a, b, i});
}
for (auto& a : graph) {
sort(begin(a), end(a));
a.erase(unique(begin(a), end(a)), a.end());
}
vector<C> dp[n];
dp[0].emplace_back(0, 0);
for (int i = 0; i < n; i++) {
dp[i] = lower_convex_hull(dp[i]);
for (auto& [a, b, qi] : queries[i]) {
qans[qi] = 2e9;
for (auto& c : dp[i]) {
qans[qi] = min(qans[qi], int(a * real(c) + b * imag(c)));
}
}
for (auto& [v, w] : graph[i]) {
C add = w ? 1i : 1;
for (auto& a : dp[i]) {
dp[v].push_back(a + add);
}
}
}
for (auto& a : qans) {
cout << a << endl;
}
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
solve();
}
详细
answer.code: In function ‘std::vector<std::complex<long int> > lower_convex_hull(std::vector<std::complex<long int> >)’: answer.code:30:24: error: ‘size’ is not a member of ‘std’ 30 | #define sz(x) int(std::size(x)) | ^~~~ answer.code:53:16: note: in expansion of macro ‘sz’ 53 | while (sz(ans) >= 2) { | ^~ answer.code: In function ‘void solve()’: answer.code:96:20: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 96 | for (auto& [a, b, qi] : queries[i]) { | ^ answer.code:102:20: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 102 | for (auto& [v, w] : graph[i]) { | ^