oj.uz

Submission #830645

# Submission time Handle Problem Language Result Execution time Memory
830645 2023-08-19T08:51:30 Z RaresFelix Robot (JOI21_ho_t4) C++17
24 / 100
 756 ms 81168 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(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 19092 KB Output is correct
2 Correct 9 ms 19012 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 12 ms 19028 KB Output is correct
6 Correct 9 ms 19028 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 11 ms 19088 KB Output is correct
9 Correct 12 ms 19668 KB Output is correct
10 Correct 12 ms 19624 KB Output is correct
11 Correct 12 ms 19412 KB Output is correct
12 Incorrect 11 ms 19464 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 133 ms 35888 KB Output is correct
2 Correct 59 ms 27736 KB Output is correct
3 Correct 152 ms 34332 KB Output is correct
4 Correct 89 ms 30420 KB Output is correct
5 Correct 756 ms 81168 KB Output is correct
6 Correct 526 ms 72032 KB Output is correct
7 Correct 251 ms 57100 KB Output is correct
8 Correct 298 ms 49372 KB Output is correct
9 Correct 303 ms 49412 KB Output is correct
10 Correct 217 ms 48496 KB Output is correct
11 Correct 146 ms 38900 KB Output is correct

Subtask #3
0 / 42.0

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