oj.uz

답안 #917749

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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 3 ms 14532 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14424 KB Output is correct
5 Correct 5 ms 14424 KB Output is correct
6 Correct 4 ms 14424 KB Output is correct
7 Correct 5 ms 14804 KB Output is correct
8 Correct 4 ms 15064 KB Output is correct
9 Correct 5 ms 15300 KB Output is correct
10 Correct 16 ms 29900 KB Output is correct
11 Correct 88 ms 128364 KB Output is correct
12 Incorrect 35 ms 54908 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 57512 KB Output is correct
2 Correct 35 ms 32348 KB Output is correct
3 Correct 264 ms 189864 KB Output is correct
4 Correct 54 ms 42892 KB Output is correct
5 Execution timed out 3054 ms 60508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 3 ms 14532 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 4 ms 14424 KB Output is correct
5 Correct 5 ms 14424 KB Output is correct
6 Correct 4 ms 14424 KB Output is correct
7 Correct 5 ms 14804 KB Output is correct
8 Correct 4 ms 15064 KB Output is correct
9 Correct 5 ms 15300 KB Output is correct
10 Correct 16 ms 29900 KB Output is correct
11 Correct 88 ms 128364 KB Output is correct
12 Incorrect 35 ms 54908 KB Output isn't correct
13 Halted 0 ms 0 KB -