Submission #483675

#	Time	Username	Problem	Language	Result	Execution time	Memory
483675		Victor	Robot (JOI21_ho_t4)	C++17	100 / 100	958 ms	83060 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n, m;
vector<pair<int, pair<int, ll>>> graph[100001];
umap<int, ll> sums[100001];
umap<int, ll> dist[100001];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> m;
    rep(i, 0, m) {
        int u, v, c;
        ll w;
        cin >> u >> v >> c >> w;
        sums[--u][--c] += w;
        sums[--v][c] += w;

        graph[u].pb({c, {v, w}});
        graph[v].pb({c, {u, w}});
    }

    rep(i, 0, n) sort(all(graph[i]));

    set<pair<ll, ii>> pq;
    dist[0][m]=0;
    pq.insert({0, {0, m}});

    while (!pq.empty()) {
        ll d;
        int u, color;
        d = pq.begin()->first;
        tie(u, color) = pq.begin()->second;
        pq.erase(pq.begin());

        //cout<<"u = "<<u + 1<<" d = "<<d<<" color = "<<color<<endl;

        if (color == m) {
            trav(edge, graph[u]) {
                int ncolor = edge.first, v;
                ll w, sum = sums[u][ncolor];
                tie(v, w) = edge.second;
                ll add = min(w, sum - w);

                if (!dist[v].count(m)) dist[v][m] = ll(1e16);

                if (d + add < dist[v][m]) {
                    pq.erase({dist[v][m], {v, m}});
                    pq.insert({d + add, {v, m}});
                    dist[v][m] = d + add;
                }

                if (!dist[v].count(ncolor)) dist[v][ncolor] = ll(1e16);

                if (d < dist[v][ncolor]) {
                    pq.erase({dist[v][n], {v, ncolor}});
                    pq.insert({d, {v, ncolor}});
                    dist[v][ncolor] = d;
                }
            }
        }

        else {
            const auto &cur_g = graph[u];
            pair<int, pair<int, ll>> x = {color, {0, 0}};
            int start = lower_bound(all(cur_g), x) - cur_g.begin();
            x.first++;
            int stop = lower_bound(all(cur_g), x) - cur_g.begin();

            rep(i, start, stop) {
                int v;
                ll w, sum = sums[u][color];
                tie(v, w) = cur_g[i].second;
                ll add = sum - w;

                if (!dist[v].count(m)) dist[v][m] = ll(1e16);

                if (d + add < dist[v][m]) {
                    pq.erase({dist[v][m], {v, m}});
                    pq.insert({d + add, {v, m}});
                    dist[v][m] = d + add;
                }
            }
        }
    }

    if (!dist[n-1].count(m)) dist[n-1][m] = -1;
    cout<<dist[n-1][m]<<endl;
    return 0;
}

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