oj.uz

Submission #770565

# Submission time Handle Problem Language Result Execution time Memory
770565 2023-07-01T13:27:36 Z Blagoj Robot (JOI21_ho_t4) C++17
0 / 100
 3000 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()

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();
        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});
                }
            }
            continue;
        }
        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:42:27: 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]
   42 |         for (int i = 0; i < edg[place].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15944 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Correct 8 ms 15876 KB Output is correct
5 Correct 10 ms 16340 KB Output is correct
6 Correct 9 ms 15956 KB Output is correct
7 Correct 124 ms 20280 KB Output is correct
8 Correct 16 ms 17492 KB Output is correct
9 Correct 153 ms 93556 KB Output is correct
10 Correct 221 ms 103352 KB Output is correct
11 Correct 308 ms 160408 KB Output is correct
12 Correct 35 ms 28188 KB Output is correct
13 Correct 88 ms 56092 KB Output is correct
14 Correct 128 ms 75556 KB Output is correct
15 Execution timed out 3087 ms 34248 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3016 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 15956 KB Output is correct
2 Correct 9 ms 15944 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Correct 8 ms 15876 KB Output is correct
5 Correct 10 ms 16340 KB Output is correct
6 Correct 9 ms 15956 KB Output is correct
7 Correct 124 ms 20280 KB Output is correct
8 Correct 16 ms 17492 KB Output is correct
9 Correct 153 ms 93556 KB Output is correct
10 Correct 221 ms 103352 KB Output is correct
11 Correct 308 ms 160408 KB Output is correct
12 Correct 35 ms 28188 KB Output is correct
13 Correct 88 ms 56092 KB Output is correct
14 Correct 128 ms 75556 KB Output is correct
15 Execution timed out 3087 ms 34248 KB Time limit exceeded
16 Halted 0 ms 0 KB -