oj.uz

Submission #830652

# Submission time Handle Problem Language Result Execution time Memory
830652 2023-08-19T08:53:00 Z RaresFelix Robot (JOI21_ho_t4) C++17
24 / 100
 779 ms 81836 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
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(int i = 1; i <= n; ++i) {
        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 10 ms 19028 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 8 ms 19028 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 12 ms 19172 KB Output is correct
8 Correct 9 ms 19156 KB Output is correct
9 Correct 14 ms 19668 KB Output is correct
10 Correct 17 ms 19560 KB Output is correct
11 Correct 14 ms 19412 KB Output is correct
12 Incorrect 10 ms 19412 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 129 ms 35852 KB Output is correct
2 Correct 68 ms 27800 KB Output is correct
3 Correct 154 ms 34300 KB Output is correct
4 Correct 77 ms 30388 KB Output is correct
5 Correct 779 ms 81836 KB Output is correct
6 Correct 606 ms 70888 KB Output is correct
7 Correct 267 ms 57072 KB Output is correct
8 Correct 344 ms 49272 KB Output is correct
9 Correct 344 ms 49444 KB Output is correct
10 Correct 257 ms 48552 KB Output is correct
11 Correct 162 ms 38840 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 8 ms 19028 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 12 ms 19172 KB Output is correct
8 Correct 9 ms 19156 KB Output is correct
9 Correct 14 ms 19668 KB Output is correct
10 Correct 17 ms 19560 KB Output is correct
11 Correct 14 ms 19412 KB Output is correct
12 Incorrect 10 ms 19412 KB Output isn't correct
13 Halted 0 ms 0 KB -