oj.uz

Submission #388315

# Submission time Handle Problem Language Result Execution time Memory
388315 2021-04-10T22:27:29 Z Kepha Robot (JOI21_ho_t4) C++11
24 / 100
 1140 ms 79592 KB 
// JOI 2021 Robot
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define MX 100000
using namespace std;

struct Edge {
    int color, next;
    ll price;

    Edge (int _color = 0, int _next = 0, ll _price = 0) {
        color = _color, next = _next, price = _price;
    }
};

struct Node {
    ll dist;
    int color, cur;

    Node (ll _dist = 0, int _color = 0, int _cur = 0) {
        dist = _dist, color = _color, cur = _cur;
    }

    bool operator<(const Node& x) const { return dist > x.dist; }
};

int N, M;
map<int, vector<Edge> > adj[MX + 1];
map<int, ll> sum[MX + 1], dist2[MX + 1];
ll dist1[MX + 1];
priority_queue<Node> q;

int main() {
    // ifstream cin("tmp");

    cin >> N >> M;

    for (int i = 1; i <= M; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        adj[a][c].push_back(Edge(c, b, d));
        adj[b][c].push_back(Edge(c, a, d));   
        sum[a][c] += d;
        sum[b][c] += d;
    }

    fill(dist1 + 1, dist1 + 1 + N, INF);
    dist1[1] = 0;
    q.push(Node(0, 0, 1));

    while (q.size()) {
        int cur = q.top().cur, color = q.top().color, dist = q.top().dist;
        q.pop();
        
        if (color) {
            if (dist != dist2[cur][color]) continue;
            for (auto edge : adj[cur][color]) {
                ll cost = sum[cur][color] - edge.price;
                if (cost + dist < dist1[edge.next]) {
                    dist1[edge.next] = cost + dist;
                    q.push(Node(cost + dist, 0, edge.next));
                }
            }
        }
        else {
            if (dist != dist1[cur]) continue;
            for (auto& c : adj[cur]) {
                for (auto& edge : c.second) {
                    ll cost1 = edge.price;
                    if (cost1 + dist < dist1[edge.next]) {
                        dist1[edge.next] = cost1 + dist;
                        q.push(Node(cost1 + dist, 0, edge.next));
                    }

                    ll cost2 = sum[cur][edge.color] - edge.price;
                    if (cost2 + dist < dist1[edge.next]) {
                        dist1[edge.next] = cost2 + dist;
                        q.push(Node(cost2 + dist, 0, edge.next));
                    }

                    if (dist2[edge.next].count(edge.color) == 0 
                        || dist < dist2[edge.next][edge.color]) {
                        dist2[edge.next][edge.color] = dist;
                        q.push(Node(dist, edge.color, edge.next));
                    }
                }
            }
        }
    }

    if (dist1[N] >= INF) cout << "-1\n";
    else cout << dist1[N] << "\n";

    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14284 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 8 ms 14284 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 10 ms 14540 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 13 ms 14996 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 11 ms 14692 KB Output is correct
12 Correct 10 ms 14668 KB Output is correct
13 Correct 11 ms 14668 KB Output is correct
14 Correct 11 ms 14668 KB Output is correct
15 Incorrect 10 ms 14540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 32812 KB Output is correct
2 Correct 117 ms 24012 KB Output is correct
3 Correct 312 ms 28944 KB Output is correct
4 Correct 158 ms 26768 KB Output is correct
5 Correct 1140 ms 79592 KB Output is correct
6 Correct 885 ms 67980 KB Output is correct
7 Correct 479 ms 47988 KB Output is correct
8 Correct 609 ms 46744 KB Output is correct
9 Correct 599 ms 46916 KB Output is correct
10 Correct 433 ms 45288 KB Output is correct
11 Correct 217 ms 30752 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14284 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 8 ms 14284 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 10 ms 14540 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 13 ms 14996 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 11 ms 14692 KB Output is correct
12 Correct 10 ms 14668 KB Output is correct
13 Correct 11 ms 14668 KB Output is correct
14 Correct 11 ms 14668 KB Output is correct
15 Incorrect 10 ms 14540 KB Output isn't correct
16 Halted 0 ms 0 KB -