oj.uz

Submission #448583

# Submission time Handle Problem Language Result Execution time Memory
448583 2021-07-30T23:34:42 Z training4usaco Robot (JOI21_ho_t4) C++11
100 / 100
 553 ms 77964 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 4e5 + 10;
 
int n, m;
lint D[MAX];
vector<int> A;
vector<plint> G[MAX];
vector<pair<int, pint>> V[MAX];
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c, p; cin >> a >> b >> c >> p;
        V[a].push_back({ c, {p, b} });
        V[b].push_back({ c, {p, a} });
    }
    int sz = n;
    for (int i = 1; i < n; i++) {
        if (V[i].empty()) continue; sort(V[i].begin(), V[i].end());
        for (int l = 0, r = 0; l < V[i].size(); l = r) {
            lint s = 0;
            while (r < V[i].size() && V[i][l].va == V[i][r].va) s += V[i][r++].vb.va;
            if (r - l == 1) G[i].emplace_back(0, V[i][l].vb.vb);
            else {
                G[i].emplace_back(0, ++sz);
                for (int j = l; j < r; j++) {
                    pint x = V[i][j].vb;
                    G[i].emplace_back(x);
                    G[x.vb].emplace_back(0, sz);
                    G[sz].emplace_back(s - x.va, x.vb);
                }
            }
        }
    }
    priority_queue<plint> Q; Q.emplace(0, 1);
    for (int i = 1; i <= sz; i++) D[i] = 4e18;
    while (!Q.empty()) {
        auto t = Q.top(); Q.pop();
        if (D[t.vb] != 4e18) continue; D[t.vb] = -t.va;
        for (auto nxt : G[t.vb]) Q.emplace(t.va - nxt.va, nxt.vb);
    }
    cout << (D[n] == 4e18 ? -1 : D[n]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:25:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |         if (V[i].empty()) continue; sort(V[i].begin(), V[i].end());
      |         ^~
Main.cpp:25:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |         if (V[i].empty()) continue; sort(V[i].begin(), V[i].end());
      |                                     ^~~~
Main.cpp:26:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int l = 0, r = 0; l < V[i].size(); l = r) {
      |                                ~~^~~~~~~~~~~~~
Main.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             while (r < V[i].size() && V[i][l].va == V[i][r].va) s += V[i][r++].vb.va;
      |                    ~~^~~~~~~~~~~~~
Main.cpp:45:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   45 |         if (D[t.vb] != 4e18) continue; D[t.vb] = -t.va;
      |         ^~
Main.cpp:45:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   45 |         if (D[t.vb] != 4e18) continue; D[t.vb] = -t.va;
      |                                        ^

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 13 ms 19020 KB Output is correct
3 Correct 13 ms 19108 KB Output is correct
4 Correct 12 ms 19104 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 11 ms 19020 KB Output is correct
7 Correct 13 ms 19376 KB Output is correct
8 Correct 13 ms 19152 KB Output is correct
9 Correct 16 ms 19660 KB Output is correct
10 Correct 15 ms 19660 KB Output is correct
11 Correct 15 ms 19776 KB Output is correct
12 Correct 16 ms 19672 KB Output is correct
13 Correct 15 ms 19884 KB Output is correct
14 Correct 14 ms 19760 KB Output is correct
15 Correct 13 ms 19376 KB Output is correct
16 Correct 16 ms 19532 KB Output is correct
17 Correct 14 ms 19504 KB Output is correct
18 Correct 13 ms 19184 KB Output is correct
19 Correct 15 ms 19660 KB Output is correct
20 Correct 14 ms 19404 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 38056 KB Output is correct
2 Correct 85 ms 28096 KB Output is correct
3 Correct 312 ms 54732 KB Output is correct
4 Correct 134 ms 32048 KB Output is correct
5 Correct 415 ms 69220 KB Output is correct
6 Correct 438 ms 67956 KB Output is correct
7 Correct 377 ms 76004 KB Output is correct
8 Correct 492 ms 65172 KB Output is correct
9 Correct 542 ms 65420 KB Output is correct
10 Correct 267 ms 47132 KB Output is correct
11 Correct 151 ms 40460 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 13 ms 19020 KB Output is correct
3 Correct 13 ms 19108 KB Output is correct
4 Correct 12 ms 19104 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 11 ms 19020 KB Output is correct
7 Correct 13 ms 19376 KB Output is correct
8 Correct 13 ms 19152 KB Output is correct
9 Correct 16 ms 19660 KB Output is correct
10 Correct 15 ms 19660 KB Output is correct
11 Correct 15 ms 19776 KB Output is correct
12 Correct 16 ms 19672 KB Output is correct
13 Correct 15 ms 19884 KB Output is correct
14 Correct 14 ms 19760 KB Output is correct
15 Correct 13 ms 19376 KB Output is correct
16 Correct 16 ms 19532 KB Output is correct
17 Correct 14 ms 19504 KB Output is correct
18 Correct 13 ms 19184 KB Output is correct
19 Correct 15 ms 19660 KB Output is correct
20 Correct 14 ms 19404 KB Output is correct
21 Correct 194 ms 38056 KB Output is correct
22 Correct 85 ms 28096 KB Output is correct
23 Correct 312 ms 54732 KB Output is correct
24 Correct 134 ms 32048 KB Output is correct
25 Correct 415 ms 69220 KB Output is correct
26 Correct 438 ms 67956 KB Output is correct
27 Correct 377 ms 76004 KB Output is correct
28 Correct 492 ms 65172 KB Output is correct
29 Correct 542 ms 65420 KB Output is correct
30 Correct 267 ms 47132 KB Output is correct
31 Correct 151 ms 40460 KB Output is correct
32 Correct 288 ms 64328 KB Output is correct
33 Correct 290 ms 51720 KB Output is correct
34 Correct 384 ms 57132 KB Output is correct
35 Correct 312 ms 52252 KB Output is correct
36 Correct 377 ms 59544 KB Output is correct
37 Correct 413 ms 63636 KB Output is correct
38 Correct 388 ms 76104 KB Output is correct
39 Correct 353 ms 66536 KB Output is correct
40 Correct 487 ms 66468 KB Output is correct
41 Correct 530 ms 66900 KB Output is correct
42 Correct 455 ms 65324 KB Output is correct
43 Correct 184 ms 43396 KB Output is correct
44 Correct 553 ms 77964 KB Output is correct
45 Correct 398 ms 53948 KB Output is correct
46 Correct 324 ms 51660 KB Output is correct
47 Correct 443 ms 62864 KB Output is correct
48 Correct 458 ms 75464 KB Output is correct