oj.uz

답안 #773936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
773936 2023-07-05T09:45:13 Z mcdx9524 Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 126868 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int long long

const long long inf = 1e18 + 7;

struct edge {
    int to, color;
    long long price;
    int global_index;
};

struct info {
    int to;
    long long cost;
    int index, global_index;
};

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <vector <edge> > g(n);
    vector <edge> edges;
    for (int i = 0; i < m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--, b--;
        g[a].push_back({b, c, p, i});
        g[b].push_back({a, c, p, i});
        edges.push_back({-1, c, p, i});
    }
    unordered_map <int, int> total_price; 
    vector <vector <info> > cg(n);
    map <pair <int, int>, int> global;
    map <pair <int, int>, int> global_rev;
    unordered_map <int, int> global_price;
    for (int i = 0; i < n; i++) {
        for (auto [to, color, price, _] : g[i]) {
            total_price[color] += price;
        }
        int index = 0;
        for (auto [to, color, price, global_index] : g[i]) {
            global[{i, index}] = global_index;
            global_rev[{i, global_index}] = index;
            global_price[global_index] = price;
            if (price > total_price[color] - price) {
                cg[i].push_back({to, total_price[color] - price, -1, global_index});
            }
            cg[i].push_back({to, price, index, global_index});
            index++;
        }
        for (auto [to, color, price, _] : g[i]) {
            total_price[color] -= price;
        }
    }
    priority_queue <tuple <long long, int, int> > q;
    q.push({0, 0, -1});
    vector <vector <long long> > d(n);
    for (int i = 0; i < n; i++) {
        d[i].resize((int) g[i].size() + 1, inf);
    }
    d[0][0] = 0;
    while (!q.empty()) {
        auto [cost, v, id] = q.top();
        q.pop();
        if (-cost > d[v][id + 1]) {
            continue;
        }
        for (int i = 0; i < (int) cg[v].size(); i++) {
            auto [to, new_cost, index, global_index] = cg[v][i];
            int actual_index = -1;
            if (index != -1) {               
                actual_index = global_rev[{to, global_index}];
            } else if (id != -1) {
                int global_id = global[{v, id}];
                int incoming_color = edges[global_id].color;
                int outgoing_color = edges[global_index].color;
                if (incoming_color == outgoing_color) {
                    new_cost -= edges[global_id].price;
                }
            }
            if (d[to][actual_index + 1] > d[v][id + 1] + new_cost) {
                d[to][actual_index + 1] = d[v][id + 1] + new_cost;
                q.push({-d[to][actual_index + 1], to, actual_index});
            }
        }
    }
    ll mn = inf;
    for (int i = 0; i < (int) g[n - 1].size() + 1; i++) {
        mn = min(mn, d[n - 1][i]);
    }
    cout << (mn == inf ? -1 : mn) << '\n';
    return 0;
}

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 5 ms 864 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Incorrect 123 ms 1496 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 50720 KB Output is correct
2 Correct 152 ms 22176 KB Output is correct
3 Correct 1000 ms 84784 KB Output is correct
4 Correct 303 ms 33616 KB Output is correct
5 Execution timed out 3074 ms 126868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 5 ms 864 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Incorrect 123 ms 1496 KB Output isn't correct
10 Halted 0 ms 0 KB -