Submission #1161717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161717		tw20000807	Robot (JOI21_ho_t4)	C++20	0 / 100	92 ms	20668 KiB

Main

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;


void sol(){
    int n, m;
    cin >> n >> m;
    vector< vector< array<int, 3> > > g(n + 1);
    vector< vector< pii > > cnt(n + 1);

    vector< int > dis(2 * m + n + 1, llmx);
    vector< vector< pii > > num(n + 1);
    vector< int > base(n + 1);
    while(m--){
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        cnt[a].push_back({c, 0});
        cnt[b].push_back({c, 0});

        num[a].push_back({c, p});
        num[b].push_back({c, p});

        g[a].push_back({c, p, b});
        g[b].push_back({c, p, a});
    }
    for(int i = 1; i <= n; ++i){
        sort(all(g[i]));
        sort(all(cnt[i]));
        cnt[i].resize(unique(all(cnt[i])) - cnt[i].begin());
        num[i].push_back({0, 0});
        sort(all(num[i]));
        num[i].resize(unique(all(num[i])) - num[i].begin());
        base[i] = base[i - 1] + SZ(num[i - 1]);
        for(auto &[c, p, nxt] : g[i]){
            auto it = lower_bound(all(cnt[i]), pii(c, 0));
            it->Y += p;
        }
    }
    auto get = [&](int id, int c, int p) -> int {
        return base[id] + lower_bound(all(num[id]), pii(c, p)) - num[id].begin();
    };

    priority_queue< array<int, 5>, vector< array<int, 5> >, greater< array<int, 5> > > pq;

    dis[get(1, 0, 0)] = 0;
    pq.push({0, 1, 0, 0, get(1, 0, 0)});
    while(!pq.empty()){
        auto [D, cur, col, pri, nid] = pq.top(); pq.pop();
        if(dis[nid] != D) continue;
        if(cur == n){
            cout << D << "\n";
            return;
        }
        for(auto it = lower_bound(all(g[cur]), array<int, 3>{col, 0, 0}); it != g[cur].end() && (col == 0 || it->at(0) == col); ++it){
            auto [c, p, nxt] = *it;
            int id1 = get(nxt, c, p);
            int id2 = get(nxt, 0, 0);
            int al = lower_bound(all(cnt[cur]), pii(c, 0))->Y;

            if(dis[id1] > D + p){
                dis[id1] = D + p;
                pq.push({dis[id1], nxt, c, p, id1});
            }
            int wei = max(0LL, al - p - (c == col ? pri : 0));
            if(dis[id2] > D + wei){
                dis[id2] = D + wei;
                pq.push({dis[id2], nxt, 0, 0, id2});
            }
        }
    }
    cout << "-1\n";
}
/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

// 3

5 2
1 4 1 2
3 5 1 4
// -1


5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
// 1

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

// 7


*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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