Submission #635559

#	Time	Username	Problem	Language	Result	Execution time	Memory
635559		Trent	Robot (JOI21_ho_t4)	C++14	100 / 100	554 ms	113156 KiB

Main

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define open(g) string _name_ = g; freopen((_name_ + ".in").c_str(), "r", stdin); freopen((_name_ + ".out").c_str(), "w", stdout)
#define printArr(a, len) for(int asdf = 0; asdf < (len); ++asdf) cout << (a)[asdf] << ' '; cout << '\n';
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(i) i.begin(), i.end()
#define pii pair<int, int>
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define int ll

const int MN = 1e5 + 10;
const ll INF = 1e18;
struct edge{int n, c1, c2, p;};
struct node{int i, cc; ll d;}; // node, color channel (0 for none), distance
bool operator <(const node& a, const node& b){ return a.d > b.d; }
vector<edge> adj[MN];
vector<vector<edge>> ce[MN];
vector<ll> cs[MN], dis[MN];
// gp_hash_table<int, vector<edge>> ce[MN]; // colors split into channels
// gp_hash_table<int, ll> cs[MN]; // color sum of each node
// gp_hash_table<int, ll> dis[MN];
gp_hash_table<int, int> ci[MN];

signed main(){
    boost();
    int N, M; cin >> N >> M;
    REP(i, 1, N + 1) cs[i].push_back(0), dis[i].push_back(INF), ce[i].emplace_back();
    forR(i, M){
        int a, b, c, p; cin >> a >> b >> c >> p;
        if(ci[a].find(c) == ci[a].end()) ci[a][c] = ce[a].size(), cs[a].push_back(0), dis[a].push_back(INF), ce[a].emplace_back();
        if(ci[b].find(c) == ci[b].end()) ci[b][c] = ce[b].size(), cs[b].push_back(0), dis[b].push_back(INF), ce[b].emplace_back();
        adj[a].push_back({b, ci[a][c], ci[b][c], p}); adj[b].push_back({a, ci[b][c], ci[a][c], p});
    }

    REP(i, 1, N + 1){
        dis[i][0] = INF;
        for(auto [n, c1, c2, p] : adj[i]) cs[i][c1] += p, dis[i][c1] = INF, ce[i][c1].push_back({n, c1, c2, p});
    }
    priority_queue<node> dij;
    dij.push({1, 0, 0});
    dis[1][0] = 0;
    int tot = 0;
    while(!dij.empty()){
        auto [i, cc, d] = dij.top(); dij.pop();
        if(d > dis[i][cc]) continue;
        ++tot; assert(tot <= 2 * M + N);
        if(cc == 0){
            for(auto [n, c1, c2, p] : adj[i]) {
                ll oc = cs[i][c1] - p;
                if(dis[i][0] + min(oc, (ll) p) < dis[n][0]){
                    dis[n][0] = dis[i][0] + min(oc, (ll) p);
                    dij.push({n, 0, dis[n][0]});
                }
                if(c1 != 0 && dis[i][0] < dis[n][c2]){
                    dis[n][c2] = dis[i][0];
                    dij.push({n, c2, dis[n][c2]});
                }
            }
        } else {
            for(auto [n, c1, c2, p] : ce[i][cc]){
                ll cos = cs[i][cc] - p;
                if(dis[i][cc] + cos < dis[n][0]){
                    dis[n][0] = dis[i][cc] + cos;
                    dij.push({n, 0, dis[n][0]});
                }
            }
        }
    }
    cout << (dis[N][0] >= INF ? -1 : dis[N][0]) << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for(auto [n, c1, c2, p] : adj[i]) cs[i][c1] += p, dis[i][c1] = INF, ce[i][c1].push_back({n, c1, c2, p});
      |                  ^
Main.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |         auto [i, cc, d] = dij.top(); dij.pop();
      |              ^
Main.cpp:60:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |             for(auto [n, c1, c2, p] : adj[i]) {
      |                      ^
Main.cpp:72:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |             for(auto [n, c1, c2, p] : ce[i][cc]){
      |                      ^

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