oj.uz

Submission #830643

# Submission time Handle Problem Language Result Execution time Memory
830643 2023-08-19T08:49:33 Z RaresFelix Robot (JOI21_ho_t4) C++17
24 / 100
 657 ms 81164 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MN = 100001;
int n, m;
struct Edge {
    int cul, cost, dest;
};
vector<Edge> L[MN];
vector<pair<int, ll> > G[MN]; /// nod, cost
ll Cost[MN];
map<int, int> Fr[MN];
map<int, ll> Suma[MN];
map<int, pair<int, int> > Other[MN];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v, c, w; 
        cin >> u >> v >> c >> w;
        L[u].push_back({c, w, v});
        L[v].push_back({c, w, u});
    }
    for(int i = 1; i <= n; ++i) {
        for(auto it : L[i]) {
            ++Fr[i][it.cul];
            Suma[i][it.cul] += it.cost;
        }
        for(auto &it : L[i]) {
            it.cost = min((long long)it.cost, Suma[i][it.cul] - it.cost);
        }
        for(auto it : L[i]) {
            if(Fr[i][it.cul] == 1) {
                G[i].push_back(make_pair(it.dest, 0));
            }
            else {
                if(Fr[i][it.cul] == 2) {
                    if(!Other[i].count(it.cul)) Other[i][it.cul] = make_pair(it.dest, it.cost);
                    else {
                        int a = Other[i][it.cul].first, b = it.dest, cul = it.cul;
                        ll ca = Other[i][it.cul].second, cb = it.cost, c = min(ca, cb);
                        if(Fr[a][cul] == 1)
                            G[a].push_back(make_pair(b, c));
                        else 
                            G[a].push_back(make_pair(b, ca));

                        if(Fr[b][cul] == 1)
                            G[b].push_back(make_pair(a, c));
                        else
                            G[b].push_back(make_pair(a, cb));
                    }
                }
                G[i].push_back(make_pair(it.dest, it.cost));
            }
        }
    }
    priority_queue<pair<ll, int> > PQ;
    PQ.push(make_pair(0ll, 1));
    for(int i = 1; i <= n; ++i) Cost[i] = INF;
    Cost[1] = 0;
    while(!PQ.empty()) {
        ll nod = PQ.top().second, cost = - PQ.top().first;
        PQ.pop();
        if(Cost[nod] != cost) continue;
        for(auto [it, w] : G[nod]) {
            if(Cost[it] > Cost[nod] + w) {
                Cost[it] = Cost[nod] + w;
                PQ.push(make_pair(-Cost[it], it));
            }
        }
    }
    if(Cost[n] == INF) {
        cout << "-1\n";
    }  else {
        cout << Cost[n] << "\n";
    }
    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19000 KB Output is correct
2 Correct 9 ms 19068 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 9 ms 19096 KB Output is correct
6 Correct 9 ms 19028 KB Output is correct
7 Correct 10 ms 19228 KB Output is correct
8 Correct 9 ms 19156 KB Output is correct
9 Correct 12 ms 19672 KB Output is correct
10 Correct 15 ms 19668 KB Output is correct
11 Correct 11 ms 19436 KB Output is correct
12 Incorrect 11 ms 19420 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 35908 KB Output is correct
2 Correct 54 ms 27836 KB Output is correct
3 Correct 133 ms 34308 KB Output is correct
4 Correct 77 ms 30360 KB Output is correct
5 Correct 657 ms 81164 KB Output is correct
6 Correct 521 ms 72016 KB Output is correct
7 Correct 236 ms 57044 KB Output is correct
8 Correct 257 ms 49316 KB Output is correct
9 Correct 297 ms 49484 KB Output is correct
10 Correct 195 ms 48488 KB Output is correct
11 Correct 133 ms 38796 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19000 KB Output is correct
2 Correct 9 ms 19068 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 9 ms 19096 KB Output is correct
6 Correct 9 ms 19028 KB Output is correct
7 Correct 10 ms 19228 KB Output is correct
8 Correct 9 ms 19156 KB Output is correct
9 Correct 12 ms 19672 KB Output is correct
10 Correct 15 ms 19668 KB Output is correct
11 Correct 11 ms 19436 KB Output is correct
12 Incorrect 11 ms 19420 KB Output isn't correct
13 Halted 0 ms 0 KB -