oj.uz

Submission #927642

# Submission time Handle Problem Language Result Execution time Memory
927642 2024-02-15T07:56:40 Z LonlyR Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 57804 KB 
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second
 
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int dp[maxn];
vector<array<int, 3>> adj[maxn];
map<int,int> col[maxn];
map<int,ii> dpc[maxn];
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1, u, v, w, t; i <= m; i++)
    {
        cin >> u >> v >> w >> t;
        adj[u].push_back({v, w, t});
        adj[v].push_back({u, w, t});
        if (col[u].count(w)) col[u][w] = -1;
        else col[u][w] = 0;
        if (col[v].count(w)) col[v][w] = -1;
        else col[v][w] = 0;
    }
    for (int i = 1; i <= n; i++)
        for (auto p : adj[i])
        {
            int &u = col[i][p[1]];
            if (u == 0) continue;
            if (u == -1) u = p[2];
            else u += p[2];
        }
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    memset(dp, 0x3f, sizeof dp);
    int oo = dp[0];
    dp[1] = 0;
    pq.emplace(0, 1);
    while (pq.size())
    {
        int u, v;
        tie(v, u) = pq.top();
        pq.pop();
        if (v != dp[u]) continue;
        for (auto p : adj[u])
        {
            int color = p[1], cost = p[2], nxt = p[0];
            if (col[u][color] != 0)
            {
                int val = v + cost, f = 0;
                if (dp[nxt] > val)
                    dp[nxt] = val,
                    f = 1,
                    dpc[nxt][color] = {val - cost, u};
              	else if (!dpc[nxt].count(color) || dpc[nxt][color].ff > val - cost)
                    f = 1,
                    dpc[nxt][color] = {val - cost, u};
                val = v + col[u][color] - cost;
                if (dp[nxt] > val)
                    dp[nxt] = val,
                    f = 1;
                if (dpc[u].count(color) && nxt != dpc[u][color].ss)
                {
                    val = dpc[u][color].ff + col[u][color] - cost;
                    if (dp[nxt] > val)
                        dp[nxt] = val,
                        f = 1;
                }
                if (f) pq.emplace(dp[nxt], nxt);
            }
            else if (dp[nxt] > v)
                dp[nxt] = v,
                pq.emplace(dp[nxt], nxt);
        }
    }
    cout << (dp[n] == oo ? -1 : dp[n]);
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 6 ms 25508 KB Output is correct
3 Correct 5 ms 25592 KB Output is correct
4 Correct 7 ms 25436 KB Output is correct
5 Correct 5 ms 25480 KB Output is correct
6 Correct 5 ms 25436 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 5 ms 25432 KB Output is correct
9 Correct 126 ms 25968 KB Output is correct
10 Correct 57 ms 25924 KB Output is correct
11 Correct 6 ms 25688 KB Output is correct
12 Correct 6 ms 25724 KB Output is correct
13 Correct 6 ms 25692 KB Output is correct
14 Correct 6 ms 25692 KB Output is correct
15 Correct 6 ms 25552 KB Output is correct
16 Incorrect 6 ms 25692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 40756 KB Output is correct
2 Correct 41 ms 32720 KB Output is correct
3 Correct 105 ms 40916 KB Output is correct
4 Correct 56 ms 35436 KB Output is correct
5 Execution timed out 3058 ms 57804 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 6 ms 25508 KB Output is correct
3 Correct 5 ms 25592 KB Output is correct
4 Correct 7 ms 25436 KB Output is correct
5 Correct 5 ms 25480 KB Output is correct
6 Correct 5 ms 25436 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 5 ms 25432 KB Output is correct
9 Correct 126 ms 25968 KB Output is correct
10 Correct 57 ms 25924 KB Output is correct
11 Correct 6 ms 25688 KB Output is correct
12 Correct 6 ms 25724 KB Output is correct
13 Correct 6 ms 25692 KB Output is correct
14 Correct 6 ms 25692 KB Output is correct
15 Correct 6 ms 25552 KB Output is correct
16 Incorrect 6 ms 25692 KB Output isn't correct
17 Halted 0 ms 0 KB -