Submission #689357

#	Time	Username	Problem	Language	Result	Execution time	Memory
689357		JooDdae	Robot (JOI21_ho_t4)	C++17	34 / 100	3036 ms	52136 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];

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

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;
            }
            j = k;
        }
    }

    X[0] = Y[0] = 1, pq.push({0, 0, 0, 0});
    while(!pq.empty()) {
        auto [cost, id, k, type] = pq.top(); pq.pop();
        if(d[id][k][type] < cost) continue;
        int u = k ? X[id] : Y[id];
        // cout << cost << " " << type << ' ' << u << "\n";
        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});
            }
            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});
            }
            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;
        }

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

    // cout << "DIE";
    cout << -1;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29: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]
   29 |         for(int j=0;j<V.size();j++) {
      |                     ~^~~~~~~~~
Main.cpp:32: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]
   32 |             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: 0 / 24
• Subtask 3: 0 / 42