Submission #689368

#	Time	Username	Problem	Language	Result	Execution time	Memory
689368		JooDdae	Robot (JOI21_ho_t4)	C++17	100 / 100	789 ms	96972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

int n, m, X[200200], Y[200200], C[200200], P[200200];
vector<array<int, 2>> v[100100];
list<array<int, 2>> l[100100];
bool chk[100100], chk2[100100];

ll d[200200][2][2], S[200200][2];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
priority_queue<array<ll, 5>, vector<array<ll, 5>>, greater<>> pq2;

int cnt, cur[200200][2];
ll mn[400400];
vector<array<int, 2>> v2[400400];

void update(int U) {
    if(v2[U].empty()) return;
    auto [x, y] = v2[U].back();
    ll C = mn[U] + S[x][y] - P[x];
    if(C < d[x][y][1]) d[x][y][1] = C, pq2.push({C, x, y, 1, U});
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        cin >> X[i] >> Y[i] >> C[i] >> P[i];
        v[X[i]].push_back({i, 0}), v[Y[i]].push_back({i, 1});
        for(int j=0;j<2;j++) d[i][j][0] = d[i][j][1] = INF;
    }

    for(int i=1;i<=n;i++) {
        auto &V = v[i];
        sort(V.begin(), V.end(), [&](const array<int, 2> &a, const array<int, 2> &b) { return tie(C[a[0]], P[a[0]]) < tie(C[b[0]], P[b[0]]); });
        for(auto x : V) l[i].push_back(x);

        for(int j=0;j<V.size();j++) {
            int k = j;
            ll sum = P[V[j][0]];
            while(k+1 < V.size() && C[V[j][0]] == C[V[k+1][0]]) sum += P[V[++k][0]];
            for(int l=j;l<=k;l++) {
                auto [x, y] = V[l];
                S[x][y] = sum, cur[x][y] = cnt, v2[cnt].push_back({x, y});
            }
            j = k, cnt++;
        }
    }

    fill(mn, mn+cnt, INF);
    X[0] = Y[0] = 1, pq.push({0, 0, 0, 0});

    while(!pq.empty()) {
        auto [cost, id, k, type] = pq.top();

        if(!pq2.empty() && pq2.top()[0] < cost) {
            auto [cost, id, k, type, U] = pq2.top(); pq2.pop();
            if(d[id][k][type] < cost || mn[U]+S[id][k]-P[id] != cost) continue;

            pq.push({cost, id, k, type}), v2[U].pop_back();
            update(U);

            continue;
        }

        pq.pop();

        if(d[id][k][type] < cost) continue;
        int u = k ? X[id] : Y[id];
        if(u == n) return cout << cost, 0;

        if(type) {
            while(!l[u].empty() && C[l[u].front()[0]] != C[id]) {
                auto [x, y] = l[u].front(); l[u].pop_front();
                ll C1 = cost + S[x][y] - P[x];
                if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
                ll C2 = cost + P[x];
                if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
            }
            while(!l[u].empty() && C[l[u].back()[0]] != C[id]) {
                auto [x, y] = l[u].back(); l[u].pop_back();
                ll C1 = cost + S[x][y] - P[x];
                if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
                ll C2 = cost + P[x];
                if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
            }
            if(!chk2[u]) {
                for(auto [x, y] : l[u]) {
                    ll C2 = cost + P[x];
                    if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
                }
                chk2[u] = 1;
            }
            continue;
        }

        if(!chk[u]) {
            for(auto [x, y] : v[u]) {
                ll C1 = cost + S[x][y] - P[x];
                if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
                ll C2 = cost + P[x];
                if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
            }
            chk[u] = 1;
        }

        int U = cur[id][!k];
        if(v2[U].empty() || mn[U] <= cost-P[id]) continue;
        mn[U] = min(mn[U], cost-P[id]);
        update(U);

        // for(auto [x, y] : v2[U]) if(x != id) {
        //     ll C = mn[U] + S[x][y] - P[x];
        //     if(C < d[x][y][1]) d[x][y][1] = C, pq.push({C, x, y, 1});
        // }
    }

    cout << -1;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j=0;j<V.size();j++) {
      |                     ~^~~~~~~~~
Main.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             while(k+1 < V.size() && C[V[j][0]] == C[V[k+1][0]]) sum += P[V[++k][0]];
      |                   ~~~~^~~~~~~~~~

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