oj.uz

Submission #406598

# Submission time Handle Problem Language Result Execution time Memory
406598 2021-05-17T19:26:27 Z Falcon Robot (JOI21_ho_t4) C++17
100 / 100
 1300 ms 95612 KB 
#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }

#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }


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

    int N, M; cin >> N >> M;

    struct edge { int x, c; long long p; };

    vector<edge> edges(M); 
    vector<map<int, vector<int>>> adj(N);
    vector<map<int, long long>> c_sum(N);

    rep(i, M) {
        edge& e{edges[i]}; 
        int u, v; cin >> u >> v >> e.c >> e.p;
        --u, --v, --e.c;
        e.x = u ^ v;
        c_sum[u][e.c] += e.p;
        c_sum[v][e.c] += e.p;
        adj[u][e.c].push_back(i);
        adj[v][e.c].push_back(i);
    }

    priority_queue<tuple<long long, int, int>,
                   vector<tuple<long long, int, int>>,
                   greater<tuple<long long, int, int>>> pq;

    vector<map<int, long long>> dist(N);
    pq.push({0, 0, -1});

    auto add = [&](int v, int i, long long d) {
        if(dist[v].count(i)) return;
        else pq.push({d, v, i});
    };

    while(!pq.empty()) {
        auto [d, u, c] = pq.top(); pq.pop();
        if(dist[u].count(c)) continue;
        dist[u][c] = d;

        if(c == -1) {
            for(auto& l : adj[u])
                for(int i: l.second) {
                    edge e{edges[i]}; 
                    int v{e.x ^ u};
                    add(v, -1, d + c_sum[u][e.c] - e.p);
                    add(v, -1, d + e.p);
                    add(v, e.c, d);
                }
        } else {
            for(int i: adj[u][c]) {
                edge e{edges[i]}; 
                add(e.x ^ u, -1, d + c_sum[u][e.c] - e.p);
            }
        }
    }

    debug(dist);

    cout << (dist.back().count(-1) ? dist.back()[-1] : -1) << '\n';

    #ifdef DEBUG
    dbg::dout << "\nExecution time: "
              << clock() * 1000 / CLOCKS_PER_SEC 
              << "ms" << endl;
    #endif
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
Main.cpp:104:5: note: in expansion of macro 'debug'
  104 |     debug(dist);
      |     ^~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 1204 KB Output is correct
10 Correct 5 ms 972 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 3 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 3 ms 728 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 25388 KB Output is correct
2 Correct 110 ms 13600 KB Output is correct
3 Correct 362 ms 22092 KB Output is correct
4 Correct 175 ms 18252 KB Output is correct
5 Correct 1256 ms 89212 KB Output is correct
6 Correct 1025 ms 79088 KB Output is correct
7 Correct 566 ms 64592 KB Output is correct
8 Correct 479 ms 52548 KB Output is correct
9 Correct 534 ms 52676 KB Output is correct
10 Correct 437 ms 45100 KB Output is correct
11 Correct 131 ms 28624 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 1204 KB Output is correct
10 Correct 5 ms 972 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 3 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 3 ms 728 KB Output is correct
21 Correct 294 ms 25388 KB Output is correct
22 Correct 110 ms 13600 KB Output is correct
23 Correct 362 ms 22092 KB Output is correct
24 Correct 175 ms 18252 KB Output is correct
25 Correct 1256 ms 89212 KB Output is correct
26 Correct 1025 ms 79088 KB Output is correct
27 Correct 566 ms 64592 KB Output is correct
28 Correct 479 ms 52548 KB Output is correct
29 Correct 534 ms 52676 KB Output is correct
30 Correct 437 ms 45100 KB Output is correct
31 Correct 131 ms 28624 KB Output is correct
32 Correct 335 ms 27096 KB Output is correct
33 Correct 311 ms 22792 KB Output is correct
34 Correct 648 ms 47216 KB Output is correct
35 Correct 487 ms 38448 KB Output is correct
36 Correct 466 ms 54740 KB Output is correct
37 Correct 519 ms 56628 KB Output is correct
38 Correct 551 ms 65096 KB Output is correct
39 Correct 347 ms 30752 KB Output is correct
40 Correct 470 ms 53920 KB Output is correct
41 Correct 548 ms 54340 KB Output is correct
42 Correct 717 ms 65340 KB Output is correct
43 Correct 281 ms 28212 KB Output is correct
44 Correct 797 ms 42276 KB Output is correct
45 Correct 429 ms 50896 KB Output is correct
46 Correct 326 ms 49860 KB Output is correct
47 Correct 497 ms 56492 KB Output is correct
48 Correct 1300 ms 95612 KB Output is correct