oj.uz

답안 #917757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917757 2024-01-28T17:32:56 Z 406 Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 172864 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]) 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]) {
                        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]) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 4 ms 14680 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14540 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 4 ms 14624 KB Output is correct
7 Correct 5 ms 14808 KB Output is correct
8 Correct 4 ms 15064 KB Output is correct
9 Correct 6 ms 14840 KB Output is correct
10 Correct 18 ms 30668 KB Output is correct
11 Correct 96 ms 128480 KB Output is correct
12 Incorrect 39 ms 56484 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 46244 KB Output is correct
2 Correct 29 ms 25636 KB Output is correct
3 Correct 257 ms 172864 KB Output is correct
4 Correct 48 ms 35264 KB Output is correct
5 Execution timed out 3047 ms 43736 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 4 ms 14680 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14540 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 4 ms 14624 KB Output is correct
7 Correct 5 ms 14808 KB Output is correct
8 Correct 4 ms 15064 KB Output is correct
9 Correct 6 ms 14840 KB Output is correct
10 Correct 18 ms 30668 KB Output is correct
11 Correct 96 ms 128480 KB Output is correct
12 Incorrect 39 ms 56484 KB Output isn't correct
13 Halted 0 ms 0 KB -