oj.uz

Submission #770560

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

struct Node {
    int to, color, cost;
};

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

struct T {
    ll dist;
    int place, color;
};

bool operator < (T a, T b) { return a.dist < b.dist; }

void solve() {
    priority_queue<T> pq;
    pq.push({0, 1, 0});
    while (pq.size() > 0) {
        T top = pq.top();
        pq.pop();
        if (top.color) {
            if (top.dist != dp2[top.place][top.color]) continue;
            for (auto [to, color, cost] : edg[top.place][top.color]) {
                ll newCost = top.dist + sum[top.place][color] - cost;
                if (newCost < dp[to]) {
                    dp[to] = newCost;
                    pq.push({dp[to], to, 0});
                }
            }
            continue;
        }
        if (top.dist != dp[top.place]) continue;
        for (int i = 0; i < edg[top.place].size(); i++) {
            vector<Node> next = edg[top.place][i];
            for (auto [to, color, cost] : next) {
                ll newCost = top.dist + min((ll) cost, sum[top.place][color] - (ll) cost);
                if (newCost < dp[to]) {
                    dp[to] = newCost;
                    pq.push({dp[to], to, 0});
                }
                if (!dp2[to].count(color) || top.dist < dp2[to][color]) {
                    dp2[to][color] = top.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:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<Node> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < edg[top.place].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16084 KB Output is correct
2 Correct 9 ms 15968 KB Output is correct
3 Correct 8 ms 15968 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 10 ms 16312 KB Output is correct
6 Correct 8 ms 15904 KB Output is correct
7 Correct 133 ms 20340 KB Output is correct
8 Correct 16 ms 17492 KB Output is correct
9 Correct 159 ms 93492 KB Output is correct
10 Correct 208 ms 103448 KB Output is correct
11 Correct 324 ms 160416 KB Output is correct
12 Correct 32 ms 28208 KB Output is correct
13 Correct 89 ms 56012 KB Output is correct
14 Correct 129 ms 75724 KB Output is correct
15 Execution timed out 3075 ms 34264 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 3152 ms 2070384 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 16084 KB Output is correct
2 Correct 9 ms 15968 KB Output is correct
3 Correct 8 ms 15968 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 10 ms 16312 KB Output is correct
6 Correct 8 ms 15904 KB Output is correct
7 Correct 133 ms 20340 KB Output is correct
8 Correct 16 ms 17492 KB Output is correct
9 Correct 159 ms 93492 KB Output is correct
10 Correct 208 ms 103448 KB Output is correct
11 Correct 324 ms 160416 KB Output is correct
12 Correct 32 ms 28208 KB Output is correct
13 Correct 89 ms 56012 KB Output is correct
14 Correct 129 ms 75724 KB Output is correct
15 Execution timed out 3075 ms 34264 KB Time limit exceeded
16 Halted 0 ms 0 KB -