oj.uz

Submission #415698

# Submission time Handle Problem Language Result Execution time Memory
415698 2021-06-01T11:42:51 Z ruadhan Robot (JOI21_ho_t4) C++17
100 / 100
 1200 ms 84332 KB 
// #include <bits/stdc++.h>
// typedef long long ll;
// using namespace std;

// const ll INF = 1e18;

// struct Edge
// {
//     int to, c;
//     ll p;
// };

// map<int, vector<Edge>> graph[100001];
// ll dp[100001];
// map<int, ll> dp2[100001], psum[100001];

// int main()
// {
//     int N, M;
//     cin >> N >> M;
//     for (int i = 0; i < M; i++)
//     {
//         int u, v, c;
//         ll p;
//         cin >> u >> v >> c >> p;
//         graph[u][c].push_back({v, c, p});
//         graph[v][c].push_back({u, c, p});
//         psum[u][c] += p;
//         psum[v][c] += p;
//     }

//     memset(dp, 0x3f, sizeof dp);
//     dp[1] = 0;
//     using T = tuple<ll, int, int>;
//     priority_queue<T, vector<T>, greater<T>> pq;
//     pq.push({0, 1, 0});

//     while (!pq.empty())
//     {
//         ll cost;
//         int node, c;
//         tie(cost, node, c) = pq.top();
//         pq.pop();

//     }

//     return 0;
// }
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll INF = 1e18;

struct Edge
{

    int to, c;

    ll p;
};

map<int, vector<Edge>> graph[100001];

ll dp[100001];

map<int, ll> dp2[100001], psum[100001];

int main()
{

    cin.tie(0)->sync_with_stdio(0);

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {

        int u, v, c;

        ll p;

        cin >> u >> v >> c >> p;

        graph[u][c].push_back({v, c, p});

        graph[v][c].push_back({u, c, p});

        psum[u][c] += p;

        psum[v][c] += p;
    }

    memset(dp, 0x3f, sizeof dp);

    dp[1] = 0;

    priority_queue<tuple<ll, int, int>> pq;

    pq.push({0, 1, 0});

    while (pq.size())
    {

        ll cost;

        int node, c;

        tie(cost, node, c) = pq.top();

        pq.pop();

        if (c)
        {

            if (dp2[node][c] != -cost)
                continue;

            for (Edge i : graph[node][c])
            {

                // We can't flip i in this case

                ll case1 = psum[node][c] - i.p;

                if (case1 - cost < dp[i.to])
                {

                    dp[i.to] = case1 - cost;

                    pq.push({-dp[i.to], i.to, 0});
                }
            }
        }
        else
        {

            if (dp[node] != -cost)
                continue;

            for (auto &i : graph[node])
            {

                for (Edge j : i.second)
                {

                    // Case 1: We don't flip j

                    ll case1 = psum[node][j.c] - j.p - cost;

                    if (case1 < dp[j.to])
                    {

                        dp[j.to] = case1;

                        pq.push({-dp[j.to], j.to, 0});
                    }

                    // Case 2: We flip j but not another edge of the same colour

                    ll case2 = j.p - cost;

                    if (case2 < dp[j.to])
                    {

                        dp[j.to] = case2;

                        pq.push({-dp[j.to], j.to, 0});
                    }

                    // Case 3: We flip j and another edge of the same colour

                    ll case3 = -cost;

                    if (!dp2[j.to].count(j.c) || case3 < dp2[j.to][j.c])
                    {

                        dp2[j.to][j.c] = case3;

                        pq.push({-dp2[j.to][j.c], j.to, j.c});
                    }
                }
            }
        }
    }

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

    return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15180 KB Output is correct
2 Correct 10 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 10 ms 15176 KB Output is correct
5 Correct 10 ms 15180 KB Output is correct
6 Correct 10 ms 15176 KB Output is correct
7 Correct 14 ms 15320 KB Output is correct
8 Correct 13 ms 15180 KB Output is correct
9 Correct 15 ms 15804 KB Output is correct
10 Correct 18 ms 15720 KB Output is correct
11 Correct 13 ms 15524 KB Output is correct
12 Correct 14 ms 15480 KB Output is correct
13 Correct 17 ms 15564 KB Output is correct
14 Correct 12 ms 15448 KB Output is correct
15 Correct 14 ms 15372 KB Output is correct
16 Correct 15 ms 15456 KB Output is correct
17 Correct 12 ms 15564 KB Output is correct
18 Correct 12 ms 15320 KB Output is correct
19 Correct 14 ms 15448 KB Output is correct
20 Correct 14 ms 15436 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 35004 KB Output is correct
2 Correct 101 ms 25284 KB Output is correct
3 Correct 256 ms 32116 KB Output is correct
4 Correct 144 ms 28276 KB Output is correct
5 Correct 1138 ms 82364 KB Output is correct
6 Correct 999 ms 71884 KB Output is correct
7 Correct 443 ms 56324 KB Output is correct
8 Correct 495 ms 50772 KB Output is correct
9 Correct 563 ms 50948 KB Output is correct
10 Correct 428 ms 48100 KB Output is correct
11 Correct 163 ms 32672 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15180 KB Output is correct
2 Correct 10 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 10 ms 15176 KB Output is correct
5 Correct 10 ms 15180 KB Output is correct
6 Correct 10 ms 15176 KB Output is correct
7 Correct 14 ms 15320 KB Output is correct
8 Correct 13 ms 15180 KB Output is correct
9 Correct 15 ms 15804 KB Output is correct
10 Correct 18 ms 15720 KB Output is correct
11 Correct 13 ms 15524 KB Output is correct
12 Correct 14 ms 15480 KB Output is correct
13 Correct 17 ms 15564 KB Output is correct
14 Correct 12 ms 15448 KB Output is correct
15 Correct 14 ms 15372 KB Output is correct
16 Correct 15 ms 15456 KB Output is correct
17 Correct 12 ms 15564 KB Output is correct
18 Correct 12 ms 15320 KB Output is correct
19 Correct 14 ms 15448 KB Output is correct
20 Correct 14 ms 15436 KB Output is correct
21 Correct 254 ms 35004 KB Output is correct
22 Correct 101 ms 25284 KB Output is correct
23 Correct 256 ms 32116 KB Output is correct
24 Correct 144 ms 28276 KB Output is correct
25 Correct 1138 ms 82364 KB Output is correct
26 Correct 999 ms 71884 KB Output is correct
27 Correct 443 ms 56324 KB Output is correct
28 Correct 495 ms 50772 KB Output is correct
29 Correct 563 ms 50948 KB Output is correct
30 Correct 428 ms 48100 KB Output is correct
31 Correct 163 ms 32672 KB Output is correct
32 Correct 166 ms 29152 KB Output is correct
33 Correct 206 ms 29840 KB Output is correct
34 Correct 471 ms 50588 KB Output is correct
35 Correct 395 ms 41792 KB Output is correct
36 Correct 371 ms 46836 KB Output is correct
37 Correct 426 ms 49220 KB Output is correct
38 Correct 414 ms 55588 KB Output is correct
39 Correct 204 ms 32492 KB Output is correct
40 Correct 507 ms 52120 KB Output is correct
41 Correct 531 ms 52452 KB Output is correct
42 Correct 583 ms 60744 KB Output is correct
43 Correct 288 ms 37420 KB Output is correct
44 Correct 611 ms 43440 KB Output is correct
45 Correct 405 ms 47568 KB Output is correct
46 Correct 321 ms 47940 KB Output is correct
47 Correct 382 ms 49216 KB Output is correct
48 Correct 1200 ms 84332 KB Output is correct