제출 #635550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635550		Trent	Robot (JOI21_ho_t4)	C++14	58 / 100	3071 ms	374148 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")
 
const int MN = 3e5 + 10;
const ll INF = 1e16;
struct edge{int n, c, 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];
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];
 
signed main(){
    int N, M; cin >> N >> M;
    forR(i, M){
        int a, b, c, p; cin >> a >> b >> c >> p;
        adj[a].push_back({b, c, p}); adj[b].push_back({a, c, p});
    }
    REP(i, 1, N + 1){
        dis[i][0] = INF;
        for(auto [n, c, p] : adj[i]) cs[i][c] += p, dis[i][c] = INF, ce[i][c].push_back({n, c, p});
    }
    priority_queue<node> dij;
    dij.push({1, 0, 0});
    dis[1][0] = 0;
    while(!dij.empty()){
        auto [i, cc, d] = dij.top(); dij.pop();
        if(cc == 0){
            for(auto [n, c, p] : adj[i]) {
                ll oc = cs[i][c] - 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(c != 0 && dis[i][0] < dis[n][c]){
                    dis[n][c] = dis[i][0];
                    dij.push({n, c, dis[n][c]});
                }
            }
        } else {
            for(auto [n, c, 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';
}

컴파일 시 표준 에러 (stderr) 메시지

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

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