oj.uz

Submission #924559

# Submission time Handle Problem Language Result Execution time Memory
924559 2024-02-09T08:08:02 Z crafticat Training (IOI07_training) C++17
0 / 100
 300 ms 28088 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<ll,ll>;
constexpr ll inf = 1e12 + 7;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


// Custom hash function for pairs of long long
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1, T2> &pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};

// Define hash table with custom hash function
template <class K, class V>
using ht = gp_hash_table<
        K, V, pair_hash, equal_to<K>, direct_mask_range_hashing<>, linear_probe_fn<>,
        hash_standard_resize_policy<hash_exponential_size_policy<>,
                hash_load_check_resize_trigger<>, true>>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll n, m; cin >> n >> m;

    vector<vector<tuple<ll,ll,ll>>> f(n + 1);
    for (ll i = 0; i < m; ++i) {
        ll a, b, c, d; cin >> a >> b >> c >> d;
        f[a].emplace_back(c,b,d);
        f[b].emplace_back(c,a,d);
    }

    vector<vector<tuple<ll,ll,ll>>> g(n + 1);
    for (ll i = 1; i <= n; ++i) {
        for (auto [c, node, d] : f[i]) {
            g[i].emplace_back(node,d,c);
        }
    }

    priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,greater<>> pq;
    pq.emplace(0,1,0);

    vector<ll> d(n + 1,inf);
    ht<pair<long long, long long>, int> visited;



    while (!pq.empty()) {
        auto [cost, cur, par] = pq.top();pq.pop();
        if (visited[{cur,par}]) continue;
        d[cur] = min(d[cur],cost);
        visited[{cur,par}] = true;

        map<ll, ll> app;
        for (auto [child,len, c] : g[cur]) {
            if (child == par) continue;
            app[c] += len;
        }

        for (auto [child, len, c] : g[cur]) {
            if (child == par) continue;
            if (visited[{child,cur}]) continue;
            pq.emplace(cost + len,child,cur);
            pq.emplace(cost + app[c] - len,child,-cur);
        }
    }

    if (d[n] == inf) {
        cout << "-1";
        return 0;
    }
    cout << d[n];
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 28088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 5260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 2008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 8668 KB Time limit exceeded
2 Halted 0 ms 0 KB -