oj.uz

Submission #753451

# Submission time Handle Problem Language Result Execution time Memory
753451 2023-06-05T08:40:07 Z PanosPask Robot (JOI21_ho_t4) C++14
24 / 100
 1206 ms 121104 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<int, pi> pip;

struct Edge {
    int dest;
    int colour;
    int price;
};

int n, m;
vector<map<int, ll>> colourcost;
vector<map<int, bool>> visited;
vector<map<int, ll>> dist;
vector<map<int, vector<Edge>>> by_colour;

vector<vector<Edge>> adj_list;

int main(void)
{
    scanf("%d %d", &n, &m);

    adj_list.resize(n);
    colourcost.resize(n);
    dist.resize(n);
    by_colour.resize(n);
    visited.resize(n);

    for (int i = 0; i < m; i++) {
        int u, v, c, p;
        scanf("%d %d %d %d", &u, &v, &c, &p);
        u--; v--;

        colourcost[u][c] += p;
        by_colour[u][0].pb({v, c, p});
        by_colour[u][c].pb({v, c, p});

        colourcost[v][c] += p;
        by_colour[v][0].pb({u, c, p});
        by_colour[v][c].pb({u, c, p});
    }

    priority_queue<pip, vector<pip>, greater<pip>> q;
    dist[0][0] = 0;
    q.push(mp(0, mp(0, 0)));

    while (!q.empty()) {
        int v, c;
        tie(v, c) = q.top().s;
        q.pop();

        if (visited[v][c])
            continue;
        visited[v][c] = true;


        for (auto e : by_colour[v][c]) {
            ll current_cost = colourcost[v][e.colour] - e.price;

            //Add normally first, by colour later
            if (c == 0)
                current_cost = min(current_cost, (ll)e.price);

            if ((dist[e.dest].find(0) == dist[e.dest].end())
                || (dist[e.dest][0] > dist[v][c] + current_cost)) {
                    dist[e.dest][0] = dist[v][c] + current_cost;
                    q.push(mp(dist[e.dest][0], mp(e.dest, 0)));
                }

            if (c == 0) {
                // Add by colour only, c has to be equal to 0
                // Force next step to be in same colour => The weight of the edge will be counted later
                if ((dist[e.dest].find(e.colour) == dist[e.dest].end())
                    || (dist[e.dest][e.colour] > dist[v][c])) {
                        dist[e.dest][e.colour] = dist[v][c];
                        q.push(mp(dist[e.dest][e.colour], mp(e.dest, e.colour)));
                    }
            }
        }
    }

    if (dist[n - 1].find(0) == dist[n - 1].end()) {
        printf("%d\n", -1);
    }
    else {
        ll ans = dist[n - 1][0];
        printf("%lld\n", ans);
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d %d %d %d", &u, &v, &c, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 2 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 35280 KB Output is correct
2 Correct 114 ms 19200 KB Output is correct
3 Correct 309 ms 28720 KB Output is correct
4 Correct 169 ms 26692 KB Output is correct
5 Correct 1206 ms 121104 KB Output is correct
6 Correct 1027 ms 107596 KB Output is correct
7 Correct 379 ms 82516 KB Output is correct
8 Correct 491 ms 86692 KB Output is correct
9 Correct 555 ms 86720 KB Output is correct
10 Correct 410 ms 60804 KB Output is correct
11 Correct 162 ms 44436 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 2 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -