oj.uz

답안 #770557

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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15888 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 10 ms 15956 KB Output is correct
4 Correct 9 ms 15868 KB Output is correct
5 Correct 11 ms 16364 KB Output is correct
6 Correct 9 ms 15984 KB Output is correct
7 Correct 20 ms 20308 KB Output is correct
8 Correct 15 ms 17528 KB Output is correct
9 Correct 157 ms 93556 KB Output is correct
10 Correct 154 ms 103372 KB Output is correct
11 Correct 246 ms 160480 KB Output is correct
12 Correct 31 ms 28224 KB Output is correct
13 Correct 78 ms 56140 KB Output is correct
14 Correct 102 ms 75572 KB Output is correct
15 Correct 52 ms 34252 KB Output is correct
16 Correct 138 ms 79180 KB Output is correct
17 Correct 105 ms 69168 KB Output is correct
18 Correct 10 ms 16640 KB Output is correct
19 Correct 40 ms 31564 KB Output is correct
20 Correct 159 ms 101736 KB Output is correct

Subtask #2
0 / 24.0

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

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15888 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 10 ms 15956 KB Output is correct
4 Correct 9 ms 15868 KB Output is correct
5 Correct 11 ms 16364 KB Output is correct
6 Correct 9 ms 15984 KB Output is correct
7 Correct 20 ms 20308 KB Output is correct
8 Correct 15 ms 17528 KB Output is correct
9 Correct 157 ms 93556 KB Output is correct
10 Correct 154 ms 103372 KB Output is correct
11 Correct 246 ms 160480 KB Output is correct
12 Correct 31 ms 28224 KB Output is correct
13 Correct 78 ms 56140 KB Output is correct
14 Correct 102 ms 75572 KB Output is correct
15 Correct 52 ms 34252 KB Output is correct
16 Correct 138 ms 79180 KB Output is correct
17 Correct 105 ms 69168 KB Output is correct
18 Correct 10 ms 16640 KB Output is correct
19 Correct 40 ms 31564 KB Output is correct
20 Correct 159 ms 101736 KB Output is correct
21 Execution timed out 3133 ms 1925636 KB Time limit exceeded
22 Halted 0 ms 0 KB -