oj.uz

Submission #393872

# Submission time Handle Problem Language Result Execution time Memory
393872 2021-04-24T18:01:43 Z nohaxjustsoflo Robot (JOI21_ho_t4) C++17
0 / 100
 664 ms 57844 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, c;
    ll p;
};

vector<edge> adj[mxN];
map<int, ll> costs[mxN]; ///at each node its edge's color sum

ll best[mxN][2]; /// node, parent changed
bool done[mxN][2]; /// node, parent changed

struct pos
{
    int i;
    int pchange;
    int pcolor;
    ll pcost;
    int prev;
    bool operator<(const pos& p) const
    {
        return pcost < p.pcost;
    }
};

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, c; ll p; cin >> u >> v >> c >> p;
        adj[u].push_back({v, c, p});
        costs[u][c] += p;
        adj[v].push_back({u, c, p});
        costs[v][c] += p;
    }
    for(int i = 0; i < mxN; i++)
    {
        best[i][0] = best[i][1] = 1e18;
    }
    best[1][0] = 0;
    priority_queue<pair<ll, pos>> q;
    q.push({0, {1, 0, 0, 0, 0}});
    ll ans = -1;
    while(!q.empty())
    {
        auto cur = q.top(); q.pop();
        ll cost = -cur.first;
        int i = cur.second.i;
        bool p = cur.second.pchange;
        int pcolor = cur.second.pcolor;
        ll pcost = cur.second.pcost;
        int prev = cur.second.prev;
        //if(done[i][p]) continue;
        //done[i][p]=1;
        if(i == n)
        {
            ans = cost;
            break;
        }
        if(p)
        {
            for(edge e : adj[i])
            {
                int j = e.j;
                ll c = e.p;
                int color = e.c;
                if(cost + c < best[j][1]) ///promeni sebe
                {
                    best[j][1] = cost + c;
                    q.push({-best[j][1], {j, 1, color, c, i}});
                }
                //if pcolor == e.color
                if(pcolor == color && prev != j)
                {
                    if(costs[i][color] - c - pcost + cost < best[j][0]) ///promeni sve ostale
                    {
                        best[j][0] = costs[i][color] - c - pcost + cost;
                        q.push({-best[j][0], {j, 0, 0, 0}});
                    }
                }
                else
                {
                    if(costs[i][color] - c + cost < best[j][0]) ///promeni sve ostale
                    {
                        best[j][0] = costs[i][color] - c + cost;
                        q.push({-best[j][0], {j, 0, 0, 0}});
                    }
                }
            }
        }
        else
        {
            for(edge e : adj[i])
            {
                int j = e.j;
                ll c = e.p;
                int color = e.c;
                if(cost + c < best[j][1]) ///promeni sebe
                {
                    best[j][1] = cost + c;
                    q.push({-best[j][1], {j, 1, color, c, i}});
                }
                if(costs[i][color] - c + cost < best[j][0]) ///promeni sve ostale
                {
                    best[j][0] = costs[i][color] - c + cost;
                    q.push({-best[j][0], {j, 0, 0, 0}});
                }
            }
        }
    }
    cout << ans;
}
/*
6 4
GGPPG
*/

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17484 KB Output is correct
2 Correct 10 ms 17484 KB Output is correct
3 Correct 12 ms 17484 KB Output is correct
4 Correct 11 ms 17484 KB Output is correct
5 Correct 11 ms 17460 KB Output is correct
6 Correct 10 ms 17484 KB Output is correct
7 Correct 10 ms 17632 KB Output is correct
8 Correct 10 ms 17612 KB Output is correct
9 Incorrect 12 ms 17868 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 30136 KB Output is correct
2 Correct 57 ms 23732 KB Output is correct
3 Correct 111 ms 30992 KB Output is correct
4 Correct 70 ms 26784 KB Output is correct
5 Incorrect 664 ms 57844 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17484 KB Output is correct
2 Correct 10 ms 17484 KB Output is correct
3 Correct 12 ms 17484 KB Output is correct
4 Correct 11 ms 17484 KB Output is correct
5 Correct 11 ms 17460 KB Output is correct
6 Correct 10 ms 17484 KB Output is correct
7 Correct 10 ms 17632 KB Output is correct
8 Correct 10 ms 17612 KB Output is correct
9 Incorrect 12 ms 17868 KB Output isn't correct
10 Halted 0 ms 0 KB -