QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75483#5458. Shortest Path Queryskittles1412Compile Error//C++142.7kb2023-02-05 12:59:012023-02-05 12:59:02

Judging History

你现在查看的是测评时间为 2023-02-05 12:59:02 的历史记录

  • [2024-06-21 12:37:03]
  • 管理员手动重测本题所有提交记录
  • [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]
  • 评测
  • [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();
}

Details

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’
   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’
  102 |         for (auto& [v, w] : graph[i]) {
      |                    ^