oj.uz

Submission #770585

# Submission time Handle Problem Language Result Execution time Memory
770585 2023-07-01T13:38:04 Z Blagoj Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 2097152 KB 
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>

using namespace std;

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

map<int, vector<tuple<int, int, int>>> edg[100001];
unordered_map<int, ll> sum[100001], dp2[100001];
ll dp[100001];
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] == 1e18) ? -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] = 1e18;
    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:39:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<std::tuple<int, int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for (int i = 0; i < edg[place].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15900 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15980 KB Output is correct
4 Correct 10 ms 15988 KB Output is correct
5 Correct 11 ms 16368 KB Output is correct
6 Correct 8 ms 15932 KB Output is correct
7 Correct 16 ms 20376 KB Output is correct
8 Correct 11 ms 17532 KB Output is correct
9 Correct 129 ms 93552 KB Output is correct
10 Correct 144 ms 103412 KB Output is correct
11 Correct 213 ms 160452 KB Output is correct
12 Correct 28 ms 28244 KB Output is correct
13 Correct 71 ms 56164 KB Output is correct
14 Correct 94 ms 75552 KB Output is correct
15 Correct 42 ms 34292 KB Output is correct
16 Correct 107 ms 79184 KB Output is correct
17 Correct 89 ms 69180 KB Output is correct
18 Correct 9 ms 16596 KB Output is correct
19 Correct 34 ms 31564 KB Output is correct
20 Correct 132 ms 101696 KB Output is correct

Subtask #2
0 / 24.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15900 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15980 KB Output is correct
4 Correct 10 ms 15988 KB Output is correct
5 Correct 11 ms 16368 KB Output is correct
6 Correct 8 ms 15932 KB Output is correct
7 Correct 16 ms 20376 KB Output is correct
8 Correct 11 ms 17532 KB Output is correct
9 Correct 129 ms 93552 KB Output is correct
10 Correct 144 ms 103412 KB Output is correct
11 Correct 213 ms 160452 KB Output is correct
12 Correct 28 ms 28244 KB Output is correct
13 Correct 71 ms 56164 KB Output is correct
14 Correct 94 ms 75552 KB Output is correct
15 Correct 42 ms 34292 KB Output is correct
16 Correct 107 ms 79184 KB Output is correct
17 Correct 89 ms 69180 KB Output is correct
18 Correct 9 ms 16596 KB Output is correct
19 Correct 34 ms 31564 KB Output is correct
20 Correct 132 ms 101696 KB Output is correct
21 Execution timed out 3012 ms 2097152 KB Time limit exceeded
22 Halted 0 ms 0 KB -