oj.uz

Submission #587990

# Submission time Handle Problem Language Result Execution time Memory
587990 2022-07-02T15:47:10 Z Peti Robot (JOI21_ho_t4) C++14
24 / 100
 1000 ms 108972 KB 
#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18;
vector<vector<pair<int, long long>>> g;
vector<map<int, int>> inds; 
int n, m;

inline int get(int x, int c){
    if(inds[x].count(c)) return inds[x][c];
    g[x].emplace_back((int)g.size(), 0);
    g.push_back(vector<pair<int, long long>>());
    inds[x][c] = (int)g.size() - 1;
    return (int)g.size() - 1;
}

vector<long long> dijkstra(){
    priority_queue<pair<long long, int>> pq;
    pq.push({0, 0});
    vector<long long> tav(g.size(), INF);
    vector<bool> volt(g.size(), false);
    tav[0] = 0;
    while(!pq.empty()){
        while(!pq.empty() && volt[pq.top().second]) pq.pop();
        if(pq.empty()) break;
        int x = pq.top().second;
        pq.pop();
        volt[x] = true;
        for(auto e : g[x]){
            if(!volt[e.first] && tav[e.first] > tav[x] + e.second){
                tav[e.first] = tav[x] + e.second;
                pq.push({-tav[e.first], e.first});
            }
        }
    }
    return tav;
}

void add(int x, int y, int c){
    g[x].emplace_back(y, c);
}

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

    cin>>n>>m;

    g.resize(n);
    inds.resize(n);
    vector<map<int, vector<pair<int, int>>>> elek(n);
    for(int i = 0; i < n; i++) inds[i][0] = i;
    for(int i = 0; i < m; i++){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        --a, --b;
        elek[a][c].emplace_back(b, d);
        elek[b][c].emplace_back(a, d);
    }

    for(int i = 0; i < n; i++){
        for(auto p : elek[i]){
            long long ossz = 0;
            for(auto e : p.second) ossz += e.second;
            for(auto e : p.second){
                add(get(i, p.first), get(e.first, 0), ossz - e.second);
                add(get(i, 0), get(e.first, 0), e.second);
                add(get(i, 0), get(e.first, p.first), 0);
            }
        }
    }

    long long d = dijkstra()[n-1];
    cout<<(d < INF ? d : -1)<<'\n';

    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 33704 KB Output is correct
2 Correct 75 ms 16884 KB Output is correct
3 Correct 219 ms 36244 KB Output is correct
4 Correct 126 ms 23284 KB Output is correct
5 Correct 1000 ms 108972 KB Output is correct
6 Correct 719 ms 97648 KB Output is correct
7 Correct 365 ms 81244 KB Output is correct
8 Correct 514 ms 75860 KB Output is correct
9 Correct 516 ms 75880 KB Output is correct
10 Correct 406 ms 57684 KB Output is correct
11 Correct 221 ms 48252 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 320 KB Output isn't correct
7 Halted 0 ms 0 KB -