oj.uz

Submission #830642

# Submission time Handle Problem Language Result Execution time Memory
830642 2023-08-19T08:48:16 Z RaresFelix Robot (JOI21_ho_t4) C++17
24 / 100
 3000 ms 1069972 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], 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(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 19028 KB Output is correct
2 Correct 11 ms 19016 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19012 KB Output is correct
5 Correct 9 ms 19028 KB Output is correct
6 Execution timed out 3055 ms 1069972 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 34996 KB Output is correct
2 Correct 63 ms 27332 KB Output is correct
3 Correct 141 ms 33852 KB Output is correct
4 Correct 75 ms 29900 KB Output is correct
5 Correct 638 ms 76504 KB Output is correct
6 Correct 540 ms 72824 KB Output is correct
7 Correct 240 ms 59508 KB Output is correct
8 Correct 275 ms 51880 KB Output is correct
9 Correct 308 ms 52000 KB Output is correct
10 Correct 195 ms 48992 KB Output is correct
11 Correct 135 ms 39576 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 11 ms 19016 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19012 KB Output is correct
5 Correct 9 ms 19028 KB Output is correct
6 Execution timed out 3055 ms 1069972 KB Time limit exceeded
7 Halted 0 ms 0 KB -