oj.uz

Submission #925316

# Submission time Handle Problem Language Result Execution time Memory
925316 2024-02-11T11:50:53 Z crafticat Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 312680 KB 
#include <bits/stdc++.h>

using namespace std;

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

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);
    vector<map<ll,ll>> apps(n + 1);
    map<pii, pii> roads;

    for (ll i = 1; i <= n; ++i) {
        map<ll, ll> app;
        for (auto [c, node, d] : f[i]) {
            app[c]+=d;
        }

        apps[i] = app;

        for (auto [c, node, d] : f[i]) {
            roads[{i,node}] = {c,d};
            roads[{node,i}] = {c,d};
            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);
    map<pii, ll> dp;
    map<pii,bool> visited;

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

        for (auto [child, len, c] : g[cur]) {
            if (child == par) continue;
            if (visited[{child,cur}]) continue;

            ll am = apps[cur][c];
            if (c == roads[{par,cur}].first) am -= roads[{par,cur}].second;
            pq.emplace(cost + len,child,cur);
            pq.emplace(cost + am - len,child,-cur);
        }
    }

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

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 1560 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 615 ms 51244 KB Output is correct
10 Correct 335 ms 27128 KB Output is correct
11 Correct 8 ms 2140 KB Output is correct
12 Incorrect 8 ms 1880 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 81976 KB Output is correct
2 Correct 529 ms 37516 KB Output is correct
3 Correct 2287 ms 119224 KB Output is correct
4 Correct 716 ms 55448 KB Output is correct
5 Execution timed out 3065 ms 312680 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 1560 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 615 ms 51244 KB Output is correct
10 Correct 335 ms 27128 KB Output is correct
11 Correct 8 ms 2140 KB Output is correct
12 Incorrect 8 ms 1880 KB Output isn't correct
13 Halted 0 ms 0 KB -