oj.uz

Submission #393908

# Submission time Handle Problem Language Result Execution time Memory
393908 2021-04-24T20:22:40 Z nohaxjustsoflo Robot (JOI21_ho_t4) C++17
100 / 100
 1097 ms 100128 KB 
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
const int mxN = 2e5+5;
const int mod = 1e9+7;

struct edge
{
    int j, color;
    ll cost;
};

map<int, vector<edge>> adj[mxN];
map<int, ll> costs[mxN];

ll dp1[mxN]; ///best to come node i
map<int, ll> dp2[mxN]; ///best to come to node i with color c

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int u, v, color; ll cost; cin >> u >> v >> color >> cost;
        adj[u][color].push_back({v, color, cost});
        costs[u][color] += cost;
        adj[v][color].push_back({u, color, cost});
        costs[v][color] += cost;
    }
    for(int i = 0; i < mxN; i++)
    {
        dp1[i] = 1e18;
    }
    dp1[1] = 0;
    priority_queue<pair<ll, pair<int, int>>> q;
    q.push({0, {1, 0}});
    ll ans = 1e18;
    while(!q.empty())
    {
        auto cur = q.top(); q.pop();
        int color = cur.second.second;
        int i = cur.second.first;
        ll cost = -cur.first;
        if(i == n && color == 0)
        {
            ans = cost; break;
        }
        if(color)
        {
            if(cost > dp2[i][color]) continue;
            ///idi na sve boje color za swap sve sem te 1
            for(edge e : adj[i][color])
            {
                if(cost + costs[i][color] - e.cost < dp1[e.j]) ///1
                {
                    dp1[e.j] = cost + costs[i][e.color] - e.cost;
                    q.push({-dp1[e.j], {e.j,0}});
                }
            }
        }
        else
        {
            if(cost > dp1[i]) continue;
            ///promeni sve ostale nastavi bez colora 1
            ///promeni sebe instant 2
            ///promeni sebe al na ler 3
            for(auto mp : adj[i])
            {
                for(edge e : mp.second)
                {
                    if(cost + e.cost < dp1[e.j]) /// 2
                    {
                        dp1[e.j] = cost + e.cost;
                        q.push({-dp1[e.j], {e.j, 0}});
                    }
                    if(cost + costs[i][e.color] - e.cost < dp1[e.j]) ///1
                    {
                        dp1[e.j] = cost + costs[i][e.color] - e.cost;
                        q.push({-dp1[e.j], {e.j,0}});
                    }
                    if(dp2[e.j].find(e.color)==dp2[e.j].end() || cost < dp2[e.j][e.color])
                    {
                        dp2[e.j][e.color] = cost;
                        q.push({-cost, {e.j, e.color}});
                    }
                }
            }
        }
    }
    if(ans > 1e17) cout << "-1";
    else cout << ans;
}
/*
6 4
GGPPG
*/

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30028 KB Output is correct
2 Correct 19 ms 30056 KB Output is correct
3 Correct 19 ms 30028 KB Output is correct
4 Correct 19 ms 30028 KB Output is correct
5 Correct 20 ms 30072 KB Output is correct
6 Correct 19 ms 30056 KB Output is correct
7 Correct 20 ms 30156 KB Output is correct
8 Correct 22 ms 30080 KB Output is correct
9 Correct 23 ms 30668 KB Output is correct
10 Correct 22 ms 30632 KB Output is correct
11 Correct 20 ms 30452 KB Output is correct
12 Correct 20 ms 30296 KB Output is correct
13 Correct 20 ms 30412 KB Output is correct
14 Correct 19 ms 30412 KB Output is correct
15 Correct 18 ms 30284 KB Output is correct
16 Correct 20 ms 30300 KB Output is correct
17 Correct 20 ms 30436 KB Output is correct
18 Correct 21 ms 30252 KB Output is correct
19 Correct 20 ms 30288 KB Output is correct
20 Correct 19 ms 30308 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 48300 KB Output is correct
2 Correct 94 ms 39484 KB Output is correct
3 Correct 185 ms 42932 KB Output is correct
4 Correct 99 ms 40384 KB Output is correct
5 Correct 1064 ms 94488 KB Output is correct
6 Correct 772 ms 83676 KB Output is correct
7 Correct 363 ms 64416 KB Output is correct
8 Correct 446 ms 61852 KB Output is correct
9 Correct 475 ms 61804 KB Output is correct
10 Correct 365 ms 60728 KB Output is correct
11 Correct 152 ms 45776 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30028 KB Output is correct
2 Correct 19 ms 30056 KB Output is correct
3 Correct 19 ms 30028 KB Output is correct
4 Correct 19 ms 30028 KB Output is correct
5 Correct 20 ms 30072 KB Output is correct
6 Correct 19 ms 30056 KB Output is correct
7 Correct 20 ms 30156 KB Output is correct
8 Correct 22 ms 30080 KB Output is correct
9 Correct 23 ms 30668 KB Output is correct
10 Correct 22 ms 30632 KB Output is correct
11 Correct 20 ms 30452 KB Output is correct
12 Correct 20 ms 30296 KB Output is correct
13 Correct 20 ms 30412 KB Output is correct
14 Correct 19 ms 30412 KB Output is correct
15 Correct 18 ms 30284 KB Output is correct
16 Correct 20 ms 30300 KB Output is correct
17 Correct 20 ms 30436 KB Output is correct
18 Correct 21 ms 30252 KB Output is correct
19 Correct 20 ms 30288 KB Output is correct
20 Correct 19 ms 30308 KB Output is correct
21 Correct 205 ms 48300 KB Output is correct
22 Correct 94 ms 39484 KB Output is correct
23 Correct 185 ms 42932 KB Output is correct
24 Correct 99 ms 40384 KB Output is correct
25 Correct 1064 ms 94488 KB Output is correct
26 Correct 772 ms 83676 KB Output is correct
27 Correct 363 ms 64416 KB Output is correct
28 Correct 446 ms 61852 KB Output is correct
29 Correct 475 ms 61804 KB Output is correct
30 Correct 365 ms 60728 KB Output is correct
31 Correct 152 ms 45776 KB Output is correct
32 Correct 150 ms 44000 KB Output is correct
33 Correct 163 ms 44748 KB Output is correct
34 Correct 375 ms 64048 KB Output is correct
35 Correct 273 ms 55608 KB Output is correct
36 Correct 336 ms 61572 KB Output is correct
37 Correct 391 ms 64560 KB Output is correct
38 Correct 385 ms 72068 KB Output is correct
39 Correct 162 ms 47452 KB Output is correct
40 Correct 468 ms 67096 KB Output is correct
41 Correct 498 ms 67356 KB Output is correct
42 Correct 537 ms 75568 KB Output is correct
43 Correct 251 ms 52404 KB Output is correct
44 Correct 356 ms 56444 KB Output is correct
45 Correct 360 ms 62432 KB Output is correct
46 Correct 307 ms 62824 KB Output is correct
47 Correct 369 ms 64032 KB Output is correct
48 Correct 1097 ms 100128 KB Output is correct