oj.uz

Submission #286080

# Submission time Handle Problem Language Result Execution time Memory
286080 2020-08-30T05:20:48 Z glikcakbn Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 1201 ms 57364 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

vector<pii> gph[101010];
vector<int> agph[101010];
vector<int> bgph[101010];
bool vst[101010];
long long dist[101010];
long long dst[101010][4];
vector<int> pr[101010];

void dfs(int x)
{
    if(vst[x]) return;
    vst[x] = true;
    for(auto y : pr[x]) if(y != -1)
    {
        agph[x].push_back(y);
        bgph[y].push_back(x);
        dfs(y);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    int s, t, u, v; cin >> s >> t >> u >> v; --s; --t; --u; --v;
    for(int i = 0; i < m; ++i)
    {
        int s, e, x; cin >> s >> e >> x; --s; --e;
        gph[s].push_back({e, x});
        gph[e].push_back({s, x});
    }

    {
        for(int i = 0; i < n; ++i) dist[i] = -1;
        priority_queue<plll, vector<plll>, greater<plll>> Q;
        Q.push({0, {s, -1}});
        while(Q.size())
        {
            auto x = Q.top(); Q.pop();
            if(dist[x.ee] == -1 || dist[x.ee] == x.ff) pr[x.ee].push_back(x.rr);
            if(dist[x.ee] != -1) continue;
            dist[x.ee] = x.ff;
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, x.ee}});
        }
        dfs(t);
    }

    for(int i = 0; i < n; ++i) for(int j = 0; j < 4; ++j) dst[i][j] = -1;
    priority_queue<plll, vector<plll>, greater<plll>> Q;
    Q.push({0, {u, 0}});
    while(Q.size())
    {
        auto x = Q.top(); Q.pop();
        if(dst[x.ee][x.rr] != -1) continue;
        dst[x.ee][x.rr] = x.ff;

        if(x.rr == 0)
        {
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 0}});
            for(auto y : agph[x.ee]) Q.push({x.ff, {y, 1}});
            for(auto y : bgph[x.ee]) Q.push({x.ff, {y, 2}});
        }
        else if(x.rr == 1)
        {
            for(auto y : agph[x.ee]) Q.push({x.ff, {y, 1}});
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 3}});
        }
        else if(x.rr == 2)
        {
            for(auto y : bgph[x.ee]) Q.push({x.ff, {y, 2}});
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 3}});
        }
        else for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 3}});
    }

    long long ans = (long long)8e18;
    for(int i = 0; i < 4; ++i) if(dst[v][i] != -1) ans = min(ans, dst[v][i]);
    cout << ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 41480 KB Output is correct
2 Correct 709 ms 43544 KB Output is correct
3 Correct 839 ms 43912 KB Output is correct
4 Correct 596 ms 41496 KB Output is correct
5 Correct 824 ms 38888 KB Output is correct
6 Correct 629 ms 41480 KB Output is correct
7 Correct 880 ms 45608 KB Output is correct
8 Correct 837 ms 45084 KB Output is correct
9 Correct 641 ms 41504 KB Output is correct
10 Correct 580 ms 41424 KB Output is correct
11 Correct 295 ms 28908 KB Output is correct
12 Correct 627 ms 41640 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 45136 KB Output is correct
2 Correct 744 ms 39636 KB Output is correct
3 Correct 698 ms 38964 KB Output is correct
4 Correct 745 ms 39372 KB Output is correct
5 Correct 767 ms 40416 KB Output is correct
6 Correct 824 ms 43012 KB Output is correct
7 Correct 932 ms 43972 KB Output is correct
8 Correct 744 ms 39460 KB Output is correct
9 Correct 766 ms 40220 KB Output is correct
10 Correct 712 ms 39064 KB Output is correct
11 Correct 351 ms 34660 KB Output is correct
12 Correct 816 ms 43536 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 14292 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 8 ms 9984 KB Output is correct
4 Correct 79 ms 16268 KB Output is correct
5 Correct 47 ms 13860 KB Output is correct
6 Correct 9 ms 10112 KB Output is correct
7 Correct 11 ms 10288 KB Output is correct
8 Correct 12 ms 10320 KB Output is correct
9 Correct 10 ms 10240 KB Output is correct
10 Correct 52 ms 14076 KB Output is correct
11 Correct 7 ms 9984 KB Output is correct
12 Correct 7 ms 9856 KB Output is correct
13 Correct 8 ms 9984 KB Output is correct
14 Correct 8 ms 9984 KB Output is correct
15 Correct 8 ms 9984 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 41480 KB Output is correct
2 Correct 709 ms 43544 KB Output is correct
3 Correct 839 ms 43912 KB Output is correct
4 Correct 596 ms 41496 KB Output is correct
5 Correct 824 ms 38888 KB Output is correct
6 Correct 629 ms 41480 KB Output is correct
7 Correct 880 ms 45608 KB Output is correct
8 Correct 837 ms 45084 KB Output is correct
9 Correct 641 ms 41504 KB Output is correct
10 Correct 580 ms 41424 KB Output is correct
11 Correct 295 ms 28908 KB Output is correct
12 Correct 627 ms 41640 KB Output is correct
13 Correct 756 ms 45136 KB Output is correct
14 Correct 744 ms 39636 KB Output is correct
15 Correct 698 ms 38964 KB Output is correct
16 Correct 745 ms 39372 KB Output is correct
17 Correct 767 ms 40416 KB Output is correct
18 Correct 824 ms 43012 KB Output is correct
19 Correct 932 ms 43972 KB Output is correct
20 Correct 744 ms 39460 KB Output is correct
21 Correct 766 ms 40220 KB Output is correct
22 Correct 712 ms 39064 KB Output is correct
23 Correct 351 ms 34660 KB Output is correct
24 Correct 816 ms 43536 KB Output is correct
25 Correct 64 ms 14292 KB Output is correct
26 Correct 8 ms 9984 KB Output is correct
27 Correct 8 ms 9984 KB Output is correct
28 Correct 79 ms 16268 KB Output is correct
29 Correct 47 ms 13860 KB Output is correct
30 Correct 9 ms 10112 KB Output is correct
31 Correct 11 ms 10288 KB Output is correct
32 Correct 12 ms 10320 KB Output is correct
33 Correct 10 ms 10240 KB Output is correct
34 Correct 52 ms 14076 KB Output is correct
35 Correct 7 ms 9984 KB Output is correct
36 Correct 7 ms 9856 KB Output is correct
37 Correct 8 ms 9984 KB Output is correct
38 Correct 8 ms 9984 KB Output is correct
39 Correct 8 ms 9984 KB Output is correct
40 Correct 723 ms 44984 KB Output is correct
41 Correct 626 ms 36900 KB Output is correct
42 Correct 621 ms 37136 KB Output is correct
43 Correct 448 ms 34796 KB Output is correct
44 Correct 463 ms 34784 KB Output is correct
45 Correct 1164 ms 45096 KB Output is correct
46 Correct 1172 ms 44832 KB Output is correct
47 Correct 608 ms 36120 KB Output is correct
48 Correct 470 ms 32372 KB Output is correct
49 Correct 664 ms 44720 KB Output is correct
50 Correct 1084 ms 43808 KB Output is correct
51 Correct 1201 ms 57364 KB Output is correct