oj.uz

Submission #489301

# Submission time Handle Problem Language Result Execution time Memory
489301 2021-11-22T07:43:38 Z Jarif_Rahman Robot (JOI21_ho_t4) C++17
100 / 100
 843 ms 102484 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e17;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<array<int, 3>>> v(n);
    for(int i = 0; i < m; i++){
        int a, b, c, p; cin >> a >> b >> c >> p; a--, b--;
        v[a].pb({b, c, p});
        v[b].pb({a, c, p});
    }
    vector<pair<int, int>> nodes;
    map<pair<int, int>, int> node_id;
    for(int i = 0; i < n; i++) nodes.pb({i, -1});
    for(int i = 0; i < n; i++){
        for(auto [x, c, p]: v[i]) nodes.pb({i, x});
    }
    for(int i = 0; i < nodes.size(); i++) node_id[nodes[i]] = i;
    vector<vector<pair<int, ll>>> g(nodes.size());
    for(int i = 0; i < n; i++){
        unordered_map<int, ll> cost;
        for(auto [x, c, p]: v[i]) cost[c]+=p;
        for(auto [x, c, p]: v[i]){
            g[i].pb({x, min((ll)p, cost[c]-p)});
            g[i].pb({node_id[{x, i}], p});
        }
    }
    for(int i = 0; i < n; i++){
        unordered_map<int, vector<pair<int, int>>> mp;
        for(auto [x, c, p]: v[i]) mp[c].pb({p, x});
        for(auto [cc, ss]: mp){
            if(ss.size() < 2) continue;
            sort(ss.rbegin(), ss.rend());
            ll s = 0;
            for(auto [p, x]: ss) s+=p;
            for(int j = 0; j < ss.size(); j++){
                ll cur = s-ss[j].f;
                if(j == 0){
                    cur-=ss[1].f;
                    g[node_id[{i, ss[j].sc}]].pb({ss[1].sc, cur});
                }
                else{
                    cur-=ss[0].f;
                    g[node_id[{i, ss[j].sc}]].pb({ss[0].sc, cur});
                }
            }
        }
    }

    vector<ll> dis(nodes.size(), inf);
    vector<bool> bl(nodes.size(), 0);
    priority_queue<pair<ll, int>> pq;
    dis[0] = 0;
    pq.push({0, 0});
    while(!pq.empty()){
        int nd = pq.top().sc; pq.pop();
        if(bl[nd]) continue;
        bl[nd] = 1;
        for(auto [x, w]: g[nd]) if(dis[nd]+w < dis[x]){
            dis[x] = dis[nd]+w;
            pq.push({-dis[x], x});
        }
    }

    ll ans = inf;
    for(int i = 0; i < nodes.size(); i++) if(nodes[i].f == n-1) ans = min(ans, dis[i]);
    if(ans >= inf) ans = -1;
    cout << ans << "\n";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < nodes.size(); i++) node_id[nodes[i]] = i;
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int j = 0; j < ss.size(); j++){
      |                            ~~^~~~~~~~~~~
Main.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < nodes.size(); i++) if(nodes[i].f == n-1) ans = min(ans, dis[i]);
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 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 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 4 ms 1228 KB Output is correct
11 Correct 4 ms 1356 KB Output is correct
12 Correct 6 ms 1156 KB Output is correct
13 Correct 4 ms 1228 KB Output is correct
14 Correct 4 ms 1228 KB Output is correct
15 Correct 2 ms 844 KB Output is correct
16 Correct 4 ms 1228 KB Output is correct
17 Correct 3 ms 1008 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 4 ms 1228 KB Output is correct
20 Correct 3 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 36768 KB Output is correct
2 Correct 103 ms 16820 KB Output is correct
3 Correct 413 ms 61236 KB Output is correct
4 Correct 151 ms 24884 KB Output is correct
5 Correct 706 ms 92112 KB Output is correct
6 Correct 669 ms 89788 KB Output is correct
7 Correct 635 ms 94016 KB Output is correct
8 Correct 769 ms 94852 KB Output is correct
9 Correct 774 ms 95004 KB Output is correct
10 Correct 415 ms 58428 KB Output is correct
11 Correct 302 ms 49408 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 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 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 4 ms 1228 KB Output is correct
11 Correct 4 ms 1356 KB Output is correct
12 Correct 6 ms 1156 KB Output is correct
13 Correct 4 ms 1228 KB Output is correct
14 Correct 4 ms 1228 KB Output is correct
15 Correct 2 ms 844 KB Output is correct
16 Correct 4 ms 1228 KB Output is correct
17 Correct 3 ms 1008 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 4 ms 1228 KB Output is correct
20 Correct 3 ms 972 KB Output is correct
21 Correct 241 ms 36768 KB Output is correct
22 Correct 103 ms 16820 KB Output is correct
23 Correct 413 ms 61236 KB Output is correct
24 Correct 151 ms 24884 KB Output is correct
25 Correct 706 ms 92112 KB Output is correct
26 Correct 669 ms 89788 KB Output is correct
27 Correct 635 ms 94016 KB Output is correct
28 Correct 769 ms 94852 KB Output is correct
29 Correct 774 ms 95004 KB Output is correct
30 Correct 415 ms 58428 KB Output is correct
31 Correct 302 ms 49408 KB Output is correct
32 Correct 471 ms 67964 KB Output is correct
33 Correct 373 ms 53956 KB Output is correct
34 Correct 545 ms 68520 KB Output is correct
35 Correct 418 ms 58868 KB Output is correct
36 Correct 454 ms 68140 KB Output is correct
37 Correct 558 ms 83328 KB Output is correct
38 Correct 625 ms 97648 KB Output is correct
39 Correct 556 ms 78768 KB Output is correct
40 Correct 783 ms 96348 KB Output is correct
41 Correct 843 ms 96568 KB Output is correct
42 Correct 725 ms 89832 KB Output is correct
43 Correct 298 ms 44996 KB Output is correct
44 Correct 642 ms 92132 KB Output is correct
45 Correct 634 ms 75048 KB Output is correct
46 Correct 510 ms 69168 KB Output is correct
47 Correct 618 ms 79840 KB Output is correct
48 Correct 790 ms 102484 KB Output is correct