Submission #568271

#	Time	Username	Problem	Language	Result	Execution time	Memory
568271		aadit_ambadkar	Robot (JOI21_ho_t4)	C++11	100 / 100	1795 ms	113100 KiB

Main

#include <bits/stdc++.h>

#define ll long long

const int MAXN = 1e5 + 10;
const int MAXM = 2e5 + 10;
const ll inf = 1e18 + 10LL;

using namespace std;

int N, M;
int color[MAXM * 2];
int j[MAXM * 2];
ll p[MAXM * 2];
map<pair<int, int>, ll> cost;
map<pair<int, int>, int> key;
vector<int> adj[MAXN];
vector<pair<int, ll>> graph[MAXM * 3];

void add(pair<int, int> nodeInf, ll val)
{
    if (cost.find(nodeInf) == cost.end())
        cost[nodeInf] = 0;
    cost[nodeInf] += val;
}

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

    cin >> N >> M;

    for (int i = 0, a, b; i < 2 * M; i += 2)
    {

        cin >> a >> b >> color[i] >> p[i];

        j[i] = b;
        j[i + 1] = a;
        color[i + 1] = color[i];
        p[i + 1] = p[i];

        add(make_pair(a, color[i]), p[i]);
        add(make_pair(b, color[i]), p[i]);

        key[make_pair(a, color[i])] = key[make_pair(b, color[i])] = 0;

        adj[a].push_back(i);
        adj[b].push_back(i + 1);
    }

    for (int i = 1; i <= N; i++)
        key[make_pair(i, 0)] = 0;

    int Key = 0;
    for (auto &e : key)
        e.second = ++Key;

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

        int x = key[make_pair(i, 0)];

        for (auto e : adj[i])
        {

            int y = key[make_pair(i, color[e])];
            int a = key[make_pair(j[e], 0)];
            int b = key[make_pair(j[e], color[e])];

            graph[a].push_back(make_pair(y, cost[make_pair(i, color[e])] - p[e]));
            graph[b].push_back(make_pair(x, 0));
            graph[a].push_back(make_pair(x, p[e]));
        }
    }

    for (auto e : key)
        if (e.first.second)
            graph[e.second].push_back(make_pair(key[make_pair(e.first.first, 0)], 0));

    vector<ll> dist(Key + 1, inf);

    int T = key[make_pair(N, 0)];

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    pq.push(make_pair(dist[T] = 0, T));

    while (!pq.empty())
    {

        int x = pq.top().second;
        ll d = pq.top().first;

        pq.pop();

        if (d != dist[x])
            continue;

        for (auto e : graph[x])
        {

            ll newD = d + e.second;
            int node = e.first;

            if (newD >= dist[node])
                continue;

            pq.push(make_pair(dist[node] = newD, node));
        }
    }

    int S = key[make_pair(1, 0)];

    if (dist[S] == inf)
        dist[S] = -1;

    cout << dist[S] << "\n";
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42