oj.uz

Submission #970703

# Submission time Handle Problem Language Result Execution time Memory
970703 2024-04-27T05:54:02 Z htphong0909 Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 118004 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

map<int, vector<pair<int, int>>> adj[100001];
unordered_map<int, int> D[100001];
unordered_map<int, int> sum[100001];
map<int, pair<int, int>> edge[100001];

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("TEST.in", "r", stdin);
    //freopen("TEST.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    map<int, vector<pair<int, int>>> test;
    for (int i = 0; i < m; i++)
    {
        int u, v, c, w;
        cin >> u >> v >> c >> w;
        adj[u][c].emplace_back(v, w);
        adj[v][c].emplace_back(u, w);
        sum[u][c] += w;
        sum[v][c] += w;
        edge[u][v] = {c, w};
        edge[v][u] = {c, w};
    }
    D[1][0] = 1;
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
    q.push({1, 1, 0});
    while (!q.empty())
    {
        int d = q.top()[0];
        int u = q.top()[1];
        int t = q.top()[2];
        //cerr << u << " " << t << " " << d - 1 << endl;
        int pc, pw;
        if (t == 0) tie(pc, pw) = make_pair(-1, 0);
        else tie(pc, pw) = edge[u][t];
        q.pop();
        for (const auto& [c, l] : adj[u])
        {
            int sz = (int)l.size();
            int s = sum[u][c];
            if (pc == c)
            {
                sz--;
                s -= pw;
            }
            for (const auto& [v, w] : l)
            {
                if (v == t) continue;
                if (D[u][t] + w < D[v][u] || !D[v][u])
                {
                    D[v][u] = D[u][t] + w;
                    q.push({D[v][u], v, u});
                }
                /*if (sz == 1 && (D[u][t] < D[v][u] || !D[v][u]))
                {
                    D[v][u] = D[u][t];
                    q.push({D[v][u], v, u});
                }*/
                if (D[u][t] + s - w < D[v][0] || !D[v][0])
                {
                    D[v][0] = D[u][t] + s - w;
                    q.push({D[v][0], v, 0});
                }
            }
        }
    }
    int ans = (int)1e18;
    for (const auto& [t, dis] : D[n]) ans = min(ans, dis);
    if (ans == (int)1e18) cout << -1;
    else cout << ans - 1;
    return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:35:13: warning: unused variable 'd' [-Wunused-variable]
   35 |         int d = q.top()[0];
      |             ^

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Correct 6 ms 20572 KB Output is correct
3 Correct 5 ms 20572 KB Output is correct
4 Correct 5 ms 20812 KB Output is correct
5 Correct 6 ms 20808 KB Output is correct
6 Correct 5 ms 20572 KB Output is correct
7 Correct 9 ms 21084 KB Output is correct
8 Correct 7 ms 20828 KB Output is correct
9 Correct 88 ms 21852 KB Output is correct
10 Correct 57 ms 21848 KB Output is correct
11 Correct 67 ms 21596 KB Output is correct
12 Correct 29 ms 21592 KB Output is correct
13 Correct 76 ms 21596 KB Output is correct
14 Correct 69 ms 21592 KB Output is correct
15 Correct 8 ms 21340 KB Output is correct
16 Correct 10 ms 21536 KB Output is correct
17 Correct 9 ms 21340 KB Output is correct
18 Correct 6 ms 21076 KB Output is correct
19 Correct 16 ms 21340 KB Output is correct
20 Correct 8 ms 21404 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 60572 KB Output is correct
2 Correct 158 ms 38576 KB Output is correct
3 Correct 950 ms 70528 KB Output is correct
4 Correct 243 ms 46628 KB Output is correct
5 Execution timed out 3075 ms 118004 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Correct 6 ms 20572 KB Output is correct
3 Correct 5 ms 20572 KB Output is correct
4 Correct 5 ms 20812 KB Output is correct
5 Correct 6 ms 20808 KB Output is correct
6 Correct 5 ms 20572 KB Output is correct
7 Correct 9 ms 21084 KB Output is correct
8 Correct 7 ms 20828 KB Output is correct
9 Correct 88 ms 21852 KB Output is correct
10 Correct 57 ms 21848 KB Output is correct
11 Correct 67 ms 21596 KB Output is correct
12 Correct 29 ms 21592 KB Output is correct
13 Correct 76 ms 21596 KB Output is correct
14 Correct 69 ms 21592 KB Output is correct
15 Correct 8 ms 21340 KB Output is correct
16 Correct 10 ms 21536 KB Output is correct
17 Correct 9 ms 21340 KB Output is correct
18 Correct 6 ms 21076 KB Output is correct
19 Correct 16 ms 21340 KB Output is correct
20 Correct 8 ms 21404 KB Output is correct
21 Correct 445 ms 60572 KB Output is correct
22 Correct 158 ms 38576 KB Output is correct
23 Correct 950 ms 70528 KB Output is correct
24 Correct 243 ms 46628 KB Output is correct
25 Execution timed out 3075 ms 118004 KB Time limit exceeded
26 Halted 0 ms 0 KB -