oj.uz

Submission #52302

# Submission time Handle Problem Language Result Execution time Memory
52302 2018-06-25T08:38:43 Z evpipis Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 1275 ms 24048 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

const int len = 1e5+5;
const ll inf = 1e16;
int n, m, s1, t1, s2, t2, best[len];
ll dis[5][len];
vector<ii> adj[len];
priority_queue<pair<ll, ii>, vector<pair<ll, ii> >, greater<pair<ll, ii> > > pq;

void dfs(int u){
    //printf("best %d\n", u);
    best[u] = 1;
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (!best[v.fi] && dis[4][v.fi]+v.se == dis[4][u])
            dfs(v.fi);
    }
}

void path(int s, int hey){
    if (!hey){
        for (int j = 1; j <= n; j++)
            dis[4][j] = inf;
    }
    else{
        for (int i = 0; i < 4; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = inf;
    }

    if (!hey){
        pq.push(mp(0, mp(4, s)));
    }
    else{
        if (best[s])
            pq.push(mp(0, mp(1, s))), pq.push(mp(0, mp(2, s)));
        else
            pq.push(mp(0, mp(0, s)));
    }

    while (!pq.empty()){
        pair<ll, ii> top = pq.top();
        pq.pop();

        int t = top.se.fi, u = top.se.se;
        ll d = top.fi;

        if (dis[t][u] != inf)
            continue;
        dis[t][u] = d;

        //printf("(%d, %d) -> %lld\n", t, u, d);

        for (int j = 0; j < adj[u].size(); j++){
            ii v = adj[u][j];
            if (t == 0){
                pq.push(mp(d+v.se, mp(0, v.fi)));
                if (best[v.fi])
                    pq.push(mp(d+v.se, mp(1, v.fi))), pq.push(mp(d+v.se, mp(2, v.fi)));
            }
            else if (t == 1){
                pq.push(mp(d+v.se, mp(3, v.fi)));
                if (best[v.fi] && dis[4][u]-dis[4][v.fi] == (ll)v.se)
                    pq.push(mp(d, mp(1, v.fi)));
            }
            else if (t == 2){
                pq.push(mp(d+v.se, mp(3, v.fi)));
                if (best[v.fi] && dis[4][u]-dis[4][v.fi] == -(ll)v.se)
                    pq.push(mp(d, mp(2, v.fi)));
            }
            else if (t == 3){
                pq.push(mp(d+v.se, mp(3, v.fi)));
            }
            else{
                pq.push(mp(d+v.se, mp(4, v.fi)));
            }
        }
    }
}

int main(){
    scanf("%d %d %d %d %d %d", &n, &m, &s1, &t1, &s2, &t2);
    for (int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    path(s1, 0);
    dfs(t1);
    path(s2, 1);

    ll ans = min(min(dis[0][t2], dis[1][t2]), min(dis[2][t2], dis[3][t2]));
    printf("%lld\n", ans);
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void path(int, int)':
commuter_pass.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d %d", &n, &m, &s1, &t1, &s2, &t2);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 15708 KB Output is correct
2 Correct 452 ms 16572 KB Output is correct
3 Correct 541 ms 23672 KB Output is correct
4 Correct 403 ms 23672 KB Output is correct
5 Correct 477 ms 23672 KB Output is correct
6 Correct 476 ms 23672 KB Output is correct
7 Correct 663 ms 23672 KB Output is correct
8 Correct 612 ms 23672 KB Output is correct
9 Correct 486 ms 23672 KB Output is correct
10 Correct 437 ms 23672 KB Output is correct
11 Correct 207 ms 23672 KB Output is correct
12 Correct 406 ms 23672 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 23672 KB Output is correct
2 Correct 595 ms 23672 KB Output is correct
3 Correct 866 ms 23672 KB Output is correct
4 Correct 499 ms 23672 KB Output is correct
5 Correct 531 ms 23672 KB Output is correct
6 Correct 1074 ms 23684 KB Output is correct
7 Correct 1082 ms 23952 KB Output is correct
8 Correct 488 ms 23952 KB Output is correct
9 Correct 511 ms 23952 KB Output is correct
10 Correct 534 ms 23952 KB Output is correct
11 Correct 371 ms 23952 KB Output is correct
12 Correct 1275 ms 24048 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24048 KB Output is correct
2 Correct 5 ms 24048 KB Output is correct
3 Correct 5 ms 24048 KB Output is correct
4 Correct 69 ms 24048 KB Output is correct
5 Correct 63 ms 24048 KB Output is correct
6 Correct 5 ms 24048 KB Output is correct
7 Incorrect 7 ms 24048 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 15708 KB Output is correct
2 Correct 452 ms 16572 KB Output is correct
3 Correct 541 ms 23672 KB Output is correct
4 Correct 403 ms 23672 KB Output is correct
5 Correct 477 ms 23672 KB Output is correct
6 Correct 476 ms 23672 KB Output is correct
7 Correct 663 ms 23672 KB Output is correct
8 Correct 612 ms 23672 KB Output is correct
9 Correct 486 ms 23672 KB Output is correct
10 Correct 437 ms 23672 KB Output is correct
11 Correct 207 ms 23672 KB Output is correct
12 Correct 406 ms 23672 KB Output is correct
13 Correct 561 ms 23672 KB Output is correct
14 Correct 595 ms 23672 KB Output is correct
15 Correct 866 ms 23672 KB Output is correct
16 Correct 499 ms 23672 KB Output is correct
17 Correct 531 ms 23672 KB Output is correct
18 Correct 1074 ms 23684 KB Output is correct
19 Correct 1082 ms 23952 KB Output is correct
20 Correct 488 ms 23952 KB Output is correct
21 Correct 511 ms 23952 KB Output is correct
22 Correct 534 ms 23952 KB Output is correct
23 Correct 371 ms 23952 KB Output is correct
24 Correct 1275 ms 24048 KB Output is correct
25 Correct 40 ms 24048 KB Output is correct
26 Correct 5 ms 24048 KB Output is correct
27 Correct 5 ms 24048 KB Output is correct
28 Correct 69 ms 24048 KB Output is correct
29 Correct 63 ms 24048 KB Output is correct
30 Correct 5 ms 24048 KB Output is correct
31 Incorrect 7 ms 24048 KB Output isn't correct
32 Halted 0 ms 0 KB -