oj.uz

Submission #917751

# Submission time Handle Problem Language Result Execution time Memory
917751 2024-01-28T17:18:47 Z 406 Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 172336 KB 
#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;

const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;

vector<ar3> adj[N];
int n, m, C[N], d[N], cnt[N], sum[N];
ar last[N];

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        FOR(i, 0, m) {
                int u, v, c, p;
                cin >> u >> v >> c >> p;
                --u, --v;
                adj[v].push_back({u, c, p});
                adj[u].push_back({v, c, p});
        }
        fill(last, last + N, ar{-1, -1});

        vector<array<int, 4>> E;
        FOR(i, 0, n) {
                for (auto [u, c, p]: adj[i]) cnt[c]++, sum[c] += p;
                for (auto &[u, c, p]: adj[i]) {
                        p = min(p, sum[c] - p);
                        if (cnt[c] == 2) {
                                if (last[c][0] == -1) last[c] = {u, p};
                                else {
                                        E.push_back({last[c][0], u, c, last[c][1]});
                                        E.push_back({u, last[c][0], c, p});
                                }
                        }
                }
                for (auto &[u, c, p]: adj[i]) for (auto &[v, cv, pv]: adj[i]) if (cv == c && (u != v)) {
                        E.push_back({u, v, c, sum[c] - pv});
                }
                for (auto [u, c, p]: adj[i]) cnt[c] = sum[c] = 0, last[c][0] = -1;
        }
        for (auto [u, v, c, p]: E)
                adj[u].push_back({v, c, p});

        fill(d + 1, d + N, INF);
        queue<int> q;
        q.push(0);
        while (q.size()) {
                int v = q.front();
                q.pop();
                for (auto [u, c, p]: adj[v]) {
                        int w = d[v] + p;
                        if (w < d[u]) {
                                q.push(u);
                                d[u] = w;
                        }
                }
        }
        cout << (d[n - 1] < INF ? d[n - 1] : -1) << '\n';
        return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 4 ms 14424 KB Output is correct
6 Correct 4 ms 14424 KB Output is correct
7 Correct 4 ms 14808 KB Output is correct
8 Correct 4 ms 15064 KB Output is correct
9 Correct 5 ms 15072 KB Output is correct
10 Correct 16 ms 29388 KB Output is correct
11 Correct 95 ms 128500 KB Output is correct
12 Incorrect 40 ms 55716 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 46776 KB Output is correct
2 Correct 27 ms 25800 KB Output is correct
3 Correct 259 ms 172336 KB Output is correct
4 Correct 47 ms 35100 KB Output is correct
5 Execution timed out 3027 ms 43764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 4 ms 14424 KB Output is correct
6 Correct 4 ms 14424 KB Output is correct
7 Correct 4 ms 14808 KB Output is correct
8 Correct 4 ms 15064 KB Output is correct
9 Correct 5 ms 15072 KB Output is correct
10 Correct 16 ms 29388 KB Output is correct
11 Correct 95 ms 128500 KB Output is correct
12 Incorrect 40 ms 55716 KB Output isn't correct
13 Halted 0 ms 0 KB -