oj.uz

Submission #393905

# Submission time Handle Problem Language Result Execution time Memory
393905 2021-04-24T20:16:52 Z nohaxjustsoflo Robot (JOI21_ho_t4) C++17
24 / 100
 3000 ms 292764 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<ll, int> 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
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29976 KB Output is correct
2 Correct 19 ms 29960 KB Output is correct
3 Correct 18 ms 30028 KB Output is correct
4 Correct 19 ms 30016 KB Output is correct
5 Execution timed out 3109 ms 292764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 48356 KB Output is correct
2 Correct 106 ms 39464 KB Output is correct
3 Correct 170 ms 42948 KB Output is correct
4 Correct 104 ms 40356 KB Output is correct
5 Correct 1059 ms 94444 KB Output is correct
6 Correct 779 ms 87600 KB Output is correct
7 Correct 370 ms 68508 KB Output is correct
8 Correct 468 ms 65744 KB Output is correct
9 Correct 482 ms 65860 KB Output is correct
10 Correct 369 ms 63156 KB Output is correct
11 Correct 167 ms 47636 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29976 KB Output is correct
2 Correct 19 ms 29960 KB Output is correct
3 Correct 18 ms 30028 KB Output is correct
4 Correct 19 ms 30016 KB Output is correct
5 Execution timed out 3109 ms 292764 KB Time limit exceeded
6 Halted 0 ms 0 KB -