Submission #934282

#	Time	Username	Problem	Language	Result	Execution time	Memory
934282		Pring	Robot (JOI21_ho_t4)	C++17	100 / 100	1398 ms	132588 KiB

Main

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

#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005, INF = 3.9e18;
int n, m, a[MXN], b[MXN], c[MXN], p[MXN];
int C;
map<int, vector<pii>> Mv[MXN];
map<int, int> Mi[MXN];
map<int, pii> Mid;
map<pii, int> Mp;
vector<int> eid[MXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<int> dis;

int DIJKSTRA(int sr, int to) {
    auto UPDATE1 = [&](int id, int len) -> void {
        debug(id);
        for (auto &e : eid[id]) {
            int i = a[e] ^ b[e] ^ id, clr = c[e];
            // debug(e, i, clr, Mp[mp(i, clr)]);
            debug(p[e], Mi[id][clr] - p[e]);
            debug(len + min(p[e], Mi[id][clr] - p[e]), i);
            pq.push(mp(len + min(p[e], Mi[id][clr] - p[e]), i));
            debug(len, Mp[mp(i, clr)]);
            pq.push(mp(len, Mp[mp(i, clr)]));
        }
    };
    auto UPDATE2 = [&](int id, int len) -> void {
        debug(2, id);
        int v = Mid[id].fs, clr = Mid[id].sc;
        for (auto &p : Mv[v][clr]) {
            int i = p.fs;
            pq.push(mp(len + Mi[v][clr] - p.sc, i));
        }
    };
    dis.resize(C + 1, -1);
    pq.push(mp(0LL, 1LL));
    while (pq.size()) {
        int len = pq.top().fs, id = pq.top().sc;
        pq.pop();
        if (dis[id] != -1) continue;
        dis[id] = len;
        debug(id, len);
        if (id == to) return dis[id];
        if (id <= n) UPDATE1(id, len);
        else UPDATE2(id, len);
    }
    return dis[to];
}

void miku() {
    cin >> n >> m;
    C = n;
    FOR(i, 0, m) {
        cin >> a[i] >> b[i] >> c[i] >> p[i];
        eid[a[i]].push_back(i);
        eid[b[i]].push_back(i);
        Mv[a[i]][c[i]].push_back(mp(b[i], p[i]));
        Mi[a[i]][c[i]] += p[i];
        Mv[b[i]][c[i]].push_back(mp(a[i], p[i]));
        Mi[b[i]][c[i]] += p[i];
    }
    // for (auto &i : eid[1]) {
        // debug(i, a[i], b[i]);
    // }
    FOR(i, 1, n + 1) {
        for (auto it = Mv[i].begin(); it != Mv[i].end(); it++) {
            // int clr = it -> fs;
            // debug(i, clr, Mi[i][clr]);
            C++;
            Mp[mp(i, it -> fs)] = C;
            Mid[C] = mp(i, it -> fs);
        }
    }
    // for (auto i : Mid) debug(i.fs, i.sc.fs, i.sc.sc);
    cout << DIJKSTRA(1, n) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:33:9: note: in expansion of macro 'debug'
   33 |         debug(id);
      |         ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:37:13: note: in expansion of macro 'debug'
   37 |             debug(p[e], Mi[id][clr] - p[e]);
      |             ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:38:13: note: in expansion of macro 'debug'
   38 |             debug(len + min(p[e], Mi[id][clr] - p[e]), i);
      |             ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:40:13: note: in expansion of macro 'debug'
   40 |             debug(len, Mp[mp(i, clr)]);
      |             ^~~~~
Main.cpp: In lambda function:
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:45:9: note: in expansion of macro 'debug'
   45 |         debug(2, id);
      |         ^~~~~
Main.cpp: In function 'long long int DIJKSTRA(long long int, long long int)':
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
Main.cpp:59:9: note: in expansion of macro 'debug'
   59 |         debug(id, len);
      |         ^~~~~

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