oj.uz

Submission #770569

# Submission time Handle Problem Language Result Execution time Memory
770569 2023-07-01T13:29:25 Z Blagoj Robot (JOI21_ho_t4) C++17
34 / 100
 1984 ms 2097152 KB 
#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

unordered_map<int, vector<tuple<int, int, int>>> edg[100005];
unordered_map<int, ll> sum[100005], dp2[100005];
ll dp[100005];
int n, m;

void solve() {
    priority_queue<tuple<ll, int, int>> pq;
    pq.push({0, 1, 0});
    while (pq.size() > 0) {
        ll dist;
        int place, color;
        tie(dist, place, color) = pq.top();
        dist *= -1;
        pq.pop();
        if (color) {
            if (dist != dp2[place][color]) continue;
            for (auto [to, color, cost] : edg[place][color]) {
                ll newCost = dist + sum[place][color] - cost;
                if (newCost < dp[to]) {
                    dp[to] = newCost;
                    pq.push({-dp[to], to, 0});
                }
            }
        }
        else {
            if (dist != dp[place]) continue;
            for (int i = 0; i < edg[place].size(); i++) {
                for (auto [to, color, cost] : edg[place][i]) {
                    ll newCost = dist + min((ll) cost, sum[place][color] - (ll) cost);
                    if (newCost < dp[to]) {
                        dp[to] = newCost;
                        pq.push({-dp[to], to, 0});
                    }
                    if (!dp2[to].count(color) || dist < dp2[to][color]) {
                        dp2[to][color] = dist;
                        pq.push({-dp2[to][color], to, color});
                    }
                }
            }
        }
    }
    cout << ((dp[n] == LLONG_MAX) ? -1 : dp[n]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 2; i <= n; i++) dp[i] = LLONG_MAX;
    for (int i = 0; i < m; i++) {
        int from, to, color, cost;
        cin >> from >> to >> color >> cost;
        edg[from][color].push_back({to, color, cost});
        edg[to][color].push_back({from, color, cost});
        sum[from][color] += cost;
        sum[to][color] += cost;
    }
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, std::vector<std::tuple<int, int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for (int i = 0; i < edg[place].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 10 ms 17076 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 14 ms 19924 KB Output is correct
8 Correct 11 ms 17876 KB Output is correct
9 Correct 77 ms 74764 KB Output is correct
10 Correct 84 ms 83400 KB Output is correct
11 Correct 123 ms 122068 KB Output is correct
12 Correct 23 ms 26196 KB Output is correct
13 Correct 43 ms 45268 KB Output is correct
14 Correct 60 ms 61396 KB Output is correct
15 Correct 27 ms 29840 KB Output is correct
16 Correct 65 ms 63444 KB Output is correct
17 Correct 54 ms 54348 KB Output is correct
18 Correct 10 ms 17308 KB Output is correct
19 Correct 23 ms 28012 KB Output is correct
20 Correct 78 ms 77036 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1984 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 10 ms 17076 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 14 ms 19924 KB Output is correct
8 Correct 11 ms 17876 KB Output is correct
9 Correct 77 ms 74764 KB Output is correct
10 Correct 84 ms 83400 KB Output is correct
11 Correct 123 ms 122068 KB Output is correct
12 Correct 23 ms 26196 KB Output is correct
13 Correct 43 ms 45268 KB Output is correct
14 Correct 60 ms 61396 KB Output is correct
15 Correct 27 ms 29840 KB Output is correct
16 Correct 65 ms 63444 KB Output is correct
17 Correct 54 ms 54348 KB Output is correct
18 Correct 10 ms 17308 KB Output is correct
19 Correct 23 ms 28012 KB Output is correct
20 Correct 78 ms 77036 KB Output is correct
21 Runtime error 1984 ms 2097152 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -