oj.uz

답안 #770572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770572 2023-07-01T13:30:00 Z Blagoj Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 2076032 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();
        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::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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15900 KB Output is correct
2 Correct 11 ms 15976 KB Output is correct
3 Correct 11 ms 15992 KB Output is correct
4 Correct 8 ms 15916 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 10 ms 16004 KB Output is correct
7 Correct 16 ms 20308 KB Output is correct
8 Correct 12 ms 17448 KB Output is correct
9 Correct 138 ms 93564 KB Output is correct
10 Correct 164 ms 103400 KB Output is correct
11 Correct 224 ms 160416 KB Output is correct
12 Correct 30 ms 28236 KB Output is correct
13 Correct 71 ms 56128 KB Output is correct
14 Correct 96 ms 75512 KB Output is correct
15 Correct 37 ms 34212 KB Output is correct
16 Correct 108 ms 79184 KB Output is correct
17 Correct 101 ms 69188 KB Output is correct
18 Correct 9 ms 16576 KB Output is correct
19 Correct 35 ms 31600 KB Output is correct
20 Correct 147 ms 101780 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3118 ms 2076032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15900 KB Output is correct
2 Correct 11 ms 15976 KB Output is correct
3 Correct 11 ms 15992 KB Output is correct
4 Correct 8 ms 15916 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 10 ms 16004 KB Output is correct
7 Correct 16 ms 20308 KB Output is correct
8 Correct 12 ms 17448 KB Output is correct
9 Correct 138 ms 93564 KB Output is correct
10 Correct 164 ms 103400 KB Output is correct
11 Correct 224 ms 160416 KB Output is correct
12 Correct 30 ms 28236 KB Output is correct
13 Correct 71 ms 56128 KB Output is correct
14 Correct 96 ms 75512 KB Output is correct
15 Correct 37 ms 34212 KB Output is correct
16 Correct 108 ms 79184 KB Output is correct
17 Correct 101 ms 69188 KB Output is correct
18 Correct 9 ms 16576 KB Output is correct
19 Correct 35 ms 31600 KB Output is correct
20 Correct 147 ms 101780 KB Output is correct
21 Execution timed out 3118 ms 2076032 KB Time limit exceeded
22 Halted 0 ms 0 KB -