Submission #1092333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092333		Octa_pe_info	Robot (JOI21_ho_t4)	C++14	34 / 100	3079 ms	36544 KiB

Main

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

const ll INF = 1e18;

struct Edge {
    long long to;
    long long c;
    ll p;
};


ll get_psum(const vector<pair<long long, ll>> &psum, long long c){
    long long left = 0, right = psum.size();
    while(left < right){
        long long mid = left + (right - left) / 2;
        if(psum[mid].first == c){
            return psum[mid].second;
        }
        else if(psum[mid].first < c){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }
    return 0;
}

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

    long long n, m;
    cin >> n >> m;


    vector<vector<Edge>> graph(n + 1, vector<Edge>());

    for(long long i = 1; i <= m; ++i){
        long long u, v, c;
        ll p;
        cin >> u >> v >> c >> p;
        graph[u].push_back(Edge{v, c, p});
        graph[v].push_back(Edge{u, c, p});
    }

    for(long long u = 1; u <= n; ++u){
        sort(graph[u].begin(), graph[u].end(), [&](const Edge &a, const Edge &b) -> bool{
            return a.c < b.c;
        });
    }

    vector<vector<pair<long long, ll>>> psum(n + 1, vector<pair<long long, ll>>());
    for(long long u = 1; u <= n; ++u){
        if(graph[u].empty()) continue;
        long long current_c = graph[u][0].c;
        ll sum_p = 0;
        for(auto &e : graph[u]){
            if(e.c != current_c){
                psum[u].emplace_back(make_pair(current_c, sum_p));
                current_c = e.c;
                sum_p = 0;
            }
            sum_p += e.p;
        }
        psum[u].emplace_back(make_pair(current_c, sum_p));
    }

    vector<ll> dp(n + 1, INF);
    dp[1] = 0;


    vector<vector<pair<long long, ll>>> dp2(n + 1, vector<pair<long long, ll>>());


    priority_queue<tuple<ll, long long, long long>, vector<tuple<ll, long long, long long>>, std::greater<tuple<ll, long long, long long>>> pq;
    pq.emplace(0, 1, 0);

    while(!pq.empty()){
        auto [cost, node, c] = pq.top(); pq.pop();

        if(c > 0){

            bool valid = false;
            ll stored_cost = INF;
            for(auto &[color, stored] : dp2[node]){
                if(color == c){
                    stored_cost = stored;
                    if(stored_cost == cost){
                        valid = true;
                    }
                    break;
                }
            }
            if(!valid){
                continue;
            }

            ll total_p = get_psum(psum[node], c);
            if(total_p == 0){
                continue;
            }

            auto &edges = graph[node];
            auto it1 = lower_bound(edges.begin(), edges.end(), c, [&](const Edge &a, long long color) -> bool{
                return a.c < color;
            });
            auto it2 = upper_bound(edges.begin(), edges.end(), c, [&](long long color, const Edge &a) -> bool{
                return color < a.c;
            });

            for(auto it = it1; it != it2; ++it){
                Edge edge = *it;
                ll new_cost = cost + (total_p - edge.p);
                if(new_cost < dp[edge.to]){
                    dp[edge.to] = new_cost;
                    pq.emplace(new_cost, edge.to, 0);
                }
            }
        }
        else{
            if(dp[node] < cost){
                continue;
            }

            for(auto &[color, sum_p] : psum[node]){
                auto &edges = graph[node];
                auto it1 = lower_bound(edges.begin(), edges.end(), color, [&](const Edge &a, long long color) -> bool{
                    return a.c < color;
                });
                auto it2 = upper_bound(edges.begin(), edges.end(), color, [&](long long color, const Edge &a) -> bool{
                    return color < a.c;
                });

                for(auto it = it1; it != it2; ++it){
                    Edge j = *it;

                    ll case1 = cost + (sum_p - j.p);
                    if(case1 < dp[j.to]){
                        dp[j.to] = case1;
                        pq.emplace(case1, j.to, 0);
                    }


                    ll case2 = cost + j.p;
                    if(case2 < dp[j.to]){
                        dp[j.to] = case2;
                        pq.emplace(case2, j.to, 0);
                    }


                    bool found = false;
                    for(auto &[existing_color, existing_cost] : dp2[j.to]){
                        if(existing_color == color){
                            if(cost < existing_cost){
                                existing_cost = cost;
                                pq.emplace(cost, j.to, color);
                            }
                            found = true;
                            break;
                        }
                    }
                    if(!found){
                        dp2[j.to].emplace_back(make_pair(color, cost));
                        pq.emplace(cost, j.to, color);
                    }
                }
            }
        }
    }

    if(dp[n] >= INF){
        cout << "-1";
    }
    else{
        cout << dp[n];
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |         auto [cost, node, c] = pq.top(); pq.pop();
      |              ^
Main.cpp:88:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |             for(auto &[color, stored] : dp2[node]){
      |                       ^
Main.cpp:128:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |             for(auto &[color, sum_p] : psum[node]){
      |                       ^
Main.cpp:155:31: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |                     for(auto &[existing_color, existing_cost] : dp2[j.to]){
      |                               ^

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