qtoq
    Logout

QOJ.ac
QOJ

    Contests
    Category
    Problems
    Submissions
    Hack!
    Blogs
    PKUTS

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#608745	#6124. King Of Zombies	qtoq	WA 	22ms	4260kb	C++17	5.1kb	2024-10-04 02:13:00	2024-10-04 02:13:01
Judging History

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

    [2024-10-04 02:13:01]评测

    测评结果：WA用时：22ms内存：4260kb

查看

    [2024-10-04 02:13:00]提交

answer

//thatsramen

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)

using ll = long long;
using ld = double;
using namespace std;
using namespace __gnu_pbds;

//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;

//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> bool mins(T& x, T y) { if (x > y) { x = y; return true; } return false; }
template<typename T> bool maxs(T& x, T y) { if (x < y) { x = y; return true; } return false; }
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set

void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
    unsyncIO(); setPrec();
    if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}

// #define TEST_CASES

struct human {
    pair<ld, ld> cord;
    pi vel;
};

void solve() {
    int n, d;
    cin >> n >> d;
    vector<human> al(n+1); 
    for (int i = 0; i <= n; i++) {
        cin >> al[i].cord.ft >> al[i].cord.sd;
        cin >> al[i].vel.ft >> al[i].vel.sd;
    }
    auto get = [&](int i, int j, ld t) -> ld {
        auto [x1, y1] = al[i].cord;
        auto [vx1, vy1] = al[i].vel;
        x1 += t * vx1;
        y1 += t * vy1;
        auto [x2, y2] = al[j].cord;
        auto [vx2, vy2] = al[j].vel;
        x2 += t * vx2;
        y2 += t * vy2;
        // if (1ll * (x2-x1) * (vy1-vy2) == 1ll * (y2-y1)*(vx1-vx2)) {
        //     if ((x2-x1 >= 0 && vx1-vx2 >= 0) || (x2-x1 >= 0 && vx1-vx2 >= 0)) {

        //     }
        // }
        ld A = (vx1 - vx2)*(vx1 - vx2) + (vy1 - vy2)*(vy1 - vy2);
        ld B = 2 * ((x1 - x2) * (vx1 - vx2) + (y1 - y2) * (vy1 - vy2));
        ld C = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) - d*d;
        if (C <= 0) {
            return 0;
        }

        // Дискриминант
        ld discriminant = B * B - 4 * A * C;

        if (discriminant < 0) {
            // Нет реального решения, нет касания
            return INF; // Возвращаем отрицательное значение как индикатор отсутствия касания
        }

        // Вычисляем два возможных момента времени касания
        ld t1 = (-B + sqrtl(discriminant)) / (2 * A);
        ld t2 = (-B - sqrtl(discriminant)) / (2 * A);

        // Нам нужно положительное время
        if (t1 >= 0 && t2 >= 0) {
            return min(t1, t2);
        } else if (t1 >= 0) {
            return t1;
        } else if (t2 >= 0) {
            return t2;
        } else {
            return INF; // Касания не произойдет
        }
        return INF;
    };
    // for (int i = 0; i <= n; i++) {
    //     auto [tx, ty] = al[i].cord;
    //     auto [vx, vy] = al[i].vel;
    //     //  dbg(i, tx +3 * vx, ty + 3 * vy);
    // }
    vector<ld> dist(n+1, INF);
    dist[0] = 0;
    priority_queue<pair<ld, int>> que;
    vector<bool> vis(n + 1, false);
    que.push({0, 0});
    while (!que.empty()) {
        auto [_, v] = que.top();
        que.pop();
        if (vis[v]) {
            continue;
        }
        vis[v] = true;
        for (int i = 1; i <= n; i++) {
            // dbg(v, i, get(v, i), dist);
            ld val = get(v, i, dist[v]);
            if (dist[i] > dist[v] + val) {
                dist[i] = dist[v] + val;
                que.push({-dist[i], i});
            }
        }
    }
    // dbg(dist);
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << -1 << '\n';
            continue;
        }
        cout << dist[i] << '\n';
    }
}

int main() {
    setIO();

    int tt = 1;
    #ifdef TEST_CASES
        cin >> tt;
    #endif

    while (tt--)
        solve();

    return 0;
}

answer.code:18:9: error: "#" is not a valid filename
   18 | #608745 #6124. King Of Zombies  qtoq    WA      22ms    4260kb  C++17   5.1kb   2024-10-04 02:13:00     2024-10-04 02:13:01
      |         ^
answer.code:3:5: error: ‘qtoq’ does not name a type
    3 |     qtoq
      |     ^~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:62,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:35:
/usr/include/c++/13/ext/type_traits.h:164:35: error: ‘constexpr const bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/13/ext/type_traits.h:159:5: note: previous declaration ‘template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)’
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/13/ext/type_traits.h:164:26: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/13/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
                 from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/type_traits:510:26: error: ‘std::size_t’ has not been declared
  510 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/13/type_traits:511:25: error: ‘_Size’ was not declared in this scope
  511 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/13/type_traits:511:31: error: template argument 1 is invalid
  511 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/13/type_traits:617:33: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’?
  617 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/13/type_traits:617:42: error: template argument 1 is invalid
  617 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/13/type_traits:621:48: error: template argument 1 is invalid
  621 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/13/type_traits:625:51: error: template argument 1 is invalid
  625 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/13/type_traits:629:57: error: template argument 1 is invalid
  629 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/13/type_traits:1348:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
 1348 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/type_traits:1348:57: error: template argument 1 is invalid
 1348 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/13/type_traits:1348:57: note: invalid template non-type parameter
/usr/include/c++/13/type_traits:1357:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
 1357 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/type_traits:1357:46: error: template argument 1 is invalid
 1357 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/13/type_traits:1357:46: note: invalid template non-type parameter
/usr/include/c++/13/type_traits:1359:26: error: ‘std::size_t’ has not been declared
 1359 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/13/type_traits:1360:21: error: ‘_Size’ was not declared in this scope
 1360 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/13/type_traits:1360:27: error: ...