oj.uz

Submission #446843

# Submission time Handle Problem Language Result Execution time Memory
446843 2021-07-23T13:19:52 Z gsc2001 Robot (JOI21_ho_t4) C++17
100 / 100
 1126 ms 87676 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define f(i, l, r) for (int i = l; i <= r; i++)
#define debug(x) cout << #x << '=' << (x) << endl
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define ff first
#define ss second

using PLL = pair<ll, ll>;
using VL = vector<ll>;
using VLL = vector<pair<ll, ll>>;

// -------------------------------------------------------------------------------
constexpr int mod = 1e9 + 7;

void setIO(const string &name = "") {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (sz(name)) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
// -------------------------------------------------------------------------------
// ------------------------Template End ------------------------------------------
// -------------------------------------------------------------------------------

struct Edge {
    ll color, changePrice, to;

    Edge(ll t, ll c, ll p) : color(c), changePrice(p), to(t) {

    }
};

constexpr ll inf = 1e18;

int main() {
    setIO();
    ll n, m;
    cin >> n >> m;
    vector<map<ll, vector<Edge>>> adj(n);
    vector<map<ll, ll>> colorCount(n);
    ll a, b, c, p;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c >> p;
        a--, b--;
        adj[a][c].push_back(Edge(b, c, p));
        adj[b][c].push_back(Edge(a, c, p));
        colorCount[a][c] += p;
        colorCount[b][c] += p;
    }

    priority_queue<tuple<ll, ll, ll>> pq;
    vector<ll> dp(n, inf);
    vector<map<ll, ll>> dp2(n);
    dp[0] = 0;
    pq.push({0, 0, 0});

    ll distNow, node;
    while (!pq.empty()) {
        tie(distNow, node, c) = pq.top();
        pq.pop();
        distNow = -distNow;
        ll newDist;
        if (c) {
            if (dp2[node][c] != distNow) continue;
            for (auto edge: adj[node][c]) {
                // I can't change this one
                newDist = dp2[node][c] + colorCount[node][c] - edge.changePrice;
                if (newDist < dp[edge.to]) {
                    dp[edge.to] = newDist;
                    pq.push({-dp[edge.to], edge.to, 0});
                }

            }
        } else {
            if (dp[node] != distNow) continue;

            for (auto &edges: adj[node]) {
                for (auto edge : edges.second) {
                    // dont change this, change others
                    newDist = dp[node] + colorCount[node][edge.color] - edge.changePrice;
                    if (newDist < dp[edge.to]) {
                        dp[edge.to] = newDist;
                        pq.push({-dp[edge.to], edge.to, 0});
                    }

                    // change this one
                    newDist = dp[node] + edge.changePrice;
                    if (newDist < dp[edge.to]) {
                        dp[edge.to] = newDist;
                        pq.push({-dp[edge.to], edge.to, 0});
                    }

                    // change this one and others for ahead one
                    newDist = dp[node];
                    if (!dp2[edge.to].count(edge.color) || newDist < dp2[edge.to][edge.color]) {
                        dp2[edge.to][edge.color] = newDist;
                        pq.push({-dp2[edge.to][edge.color], edge.to, edge.color});
                    }

                }
            }
        }

    }

    cout << (dp[n - 1] >= inf ? -1 : dp[n - 1]);


    return 0;
}

Compilation message

Main.cpp: In function 'void setIO(const string&)':
Main.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 5 ms 1100 KB Output is correct
10 Correct 4 ms 972 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 2 ms 844 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 3 ms 588 KB Output is correct
20 Correct 2 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 24176 KB Output is correct
2 Correct 80 ms 12796 KB Output is correct
3 Correct 219 ms 20540 KB Output is correct
4 Correct 142 ms 17292 KB Output is correct
5 Correct 1020 ms 82020 KB Output is correct
6 Correct 758 ms 75508 KB Output is correct
7 Correct 401 ms 63676 KB Output is correct
8 Correct 456 ms 54228 KB Output is correct
9 Correct 474 ms 54436 KB Output is correct
10 Correct 373 ms 43336 KB Output is correct
11 Correct 149 ms 32068 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 5 ms 1100 KB Output is correct
10 Correct 4 ms 972 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 2 ms 844 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 3 ms 588 KB Output is correct
20 Correct 2 ms 716 KB Output is correct
21 Correct 213 ms 24176 KB Output is correct
22 Correct 80 ms 12796 KB Output is correct
23 Correct 219 ms 20540 KB Output is correct
24 Correct 142 ms 17292 KB Output is correct
25 Correct 1020 ms 82020 KB Output is correct
26 Correct 758 ms 75508 KB Output is correct
27 Correct 401 ms 63676 KB Output is correct
28 Correct 456 ms 54228 KB Output is correct
29 Correct 474 ms 54436 KB Output is correct
30 Correct 373 ms 43336 KB Output is correct
31 Correct 149 ms 32068 KB Output is correct
32 Correct 148 ms 18732 KB Output is correct
33 Correct 193 ms 21884 KB Output is correct
34 Correct 461 ms 45068 KB Output is correct
35 Correct 339 ms 35824 KB Output is correct
36 Correct 343 ms 49712 KB Output is correct
37 Correct 390 ms 52848 KB Output is correct
38 Correct 397 ms 62884 KB Output is correct
39 Correct 167 ms 24384 KB Output is correct
40 Correct 486 ms 55580 KB Output is correct
41 Correct 504 ms 55860 KB Output is correct
42 Correct 534 ms 63380 KB Output is correct
43 Correct 251 ms 27808 KB Output is correct
44 Correct 472 ms 34388 KB Output is correct
45 Correct 355 ms 50116 KB Output is correct
46 Correct 296 ms 50008 KB Output is correct
47 Correct 361 ms 52680 KB Output is correct
48 Correct 1126 ms 87676 KB Output is correct