oj.uz

Submission #529558

# Submission time Handle Problem Language Result Execution time Memory
529558 2022-02-23T07:22:41 Z syl123456 Robot (JOI21_ho_t4) C++17
100 / 100
 1877 ms 88768 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<ll, int> pl;

struct edge {
    int u, v, c, p;
    edge(int _u, int _v, int _c, int _p) : u(_u), v(_v), c(_c), p(_p) {}
    int go(int i) {
        return u ^ v ^ i;
    }
};

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<edge> e;
    map<pi, ll> mp;
    map<pi, int> id;
    for (int i = 0; i < m; ++i) {
        int x, y, z, w;
        cin >> x >> y >> z >> w;
        --x, --y;
        g[x].push_back(e.size()), g[y].push_back(e.size());
        if (!id.count({x, z}))
            id[{x, z}] = g.size(), g.emplace_back();
        g[id[{x, z}]].push_back(e.size());
        if (!id.count({y, z}))
            id[{y, z}] = g.size(), g.emplace_back();
        g[id[{y, z}]].push_back(e.size());
        e.emplace_back(x, y, z, w);
        mp[{x, z}] += w, mp[{y, z}] += w;
    }
    vector<int> v(g.size());
    for (auto [i, j] : id)
        v[j] = i.first;
    vector<ll> dis(g.size(), INF);
    priority_queue<pl, vector<pl>, greater<pl>> pq;
    pq.emplace(0, 0);
    while (!pq.empty()) {
        int i;
        ll x;
        tie(x, i) = pq.top();
        pq.pop();
        if (dis[i] < INF)
            continue;
        dis[i] = x;
        if (i < n) {
            for (int ei : g[i])
                pq.emplace(x + min(mp[{i, e[ei].c}] - e[ei].p, (ll)e[ei].p), e[ei].go(i));
            for (int ei : g[i])
                pq.emplace(x, id[{e[ei].go(i), e[ei].c}]);
        }
        else {
            int _i = i;
            i = v[_i];
            for (int ei : g[_i])
                pq.emplace(x + mp[{i, e[ei].c}] - e[ei].p, e[ei].go(i));
        }
    }
    cout << (dis[n - 1] < INF ? dis[n - 1] : -1);
}

Compilation message

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 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 556 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 7 ms 1100 KB Output is correct
10 Correct 6 ms 972 KB Output is correct
11 Correct 4 ms 828 KB Output is correct
12 Correct 6 ms 716 KB Output is correct
13 Correct 5 ms 836 KB Output is correct
14 Correct 4 ms 844 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 3 ms 580 KB Output is correct
19 Correct 5 ms 708 KB Output is correct
20 Correct 4 ms 624 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 24260 KB Output is correct
2 Correct 184 ms 12604 KB Output is correct
3 Correct 589 ms 32228 KB Output is correct
4 Correct 258 ms 18524 KB Output is correct
5 Correct 1877 ms 87356 KB Output is correct
6 Correct 1481 ms 67896 KB Output is correct
7 Correct 783 ms 59720 KB Output is correct
8 Correct 1000 ms 35480 KB Output is correct
9 Correct 1046 ms 35704 KB Output is correct
10 Correct 762 ms 40188 KB Output is correct
11 Correct 285 ms 23784 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 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 556 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 7 ms 1100 KB Output is correct
10 Correct 6 ms 972 KB Output is correct
11 Correct 4 ms 828 KB Output is correct
12 Correct 6 ms 716 KB Output is correct
13 Correct 5 ms 836 KB Output is correct
14 Correct 4 ms 844 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 3 ms 580 KB Output is correct
19 Correct 5 ms 708 KB Output is correct
20 Correct 4 ms 624 KB Output is correct
21 Correct 556 ms 24260 KB Output is correct
22 Correct 184 ms 12604 KB Output is correct
23 Correct 589 ms 32228 KB Output is correct
24 Correct 258 ms 18524 KB Output is correct
25 Correct 1877 ms 87356 KB Output is correct
26 Correct 1481 ms 67896 KB Output is correct
27 Correct 783 ms 59720 KB Output is correct
28 Correct 1000 ms 35480 KB Output is correct
29 Correct 1046 ms 35704 KB Output is correct
30 Correct 762 ms 40188 KB Output is correct
31 Correct 285 ms 23784 KB Output is correct
32 Correct 422 ms 28624 KB Output is correct
33 Correct 422 ms 21744 KB Output is correct
34 Correct 937 ms 40088 KB Output is correct
35 Correct 723 ms 34544 KB Output is correct
36 Correct 744 ms 43668 KB Output is correct
37 Correct 767 ms 46400 KB Output is correct
38 Correct 743 ms 55444 KB Output is correct
39 Correct 465 ms 23520 KB Output is correct
40 Correct 965 ms 36964 KB Output is correct
41 Correct 1047 ms 37256 KB Output is correct
42 Correct 1254 ms 58048 KB Output is correct
43 Correct 457 ms 28508 KB Output is correct
44 Correct 1066 ms 41820 KB Output is correct
45 Correct 804 ms 33608 KB Output is correct
46 Correct 665 ms 33144 KB Output is correct
47 Correct 774 ms 45500 KB Output is correct
48 Correct 1714 ms 88768 KB Output is correct