oj.uz

Submission #930342

# Submission time Handle Problem Language Result Execution time Memory
930342 2024-02-19T12:06:23 Z fskarica Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 381 ms 42684 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

const ll MAX = 4e5 + 10;
ll n, m;
ll s, t;
ll u, v;
ll x, y, w, w2;
vector <pii> veze[MAX];
ll dis[MAX][2];
ll sol[MAX][2];
ll arr[MAX][2];
ll trm[MAX][2];
priority_queue <pii> q;

void distance(ll root, ll o) {
    priority_queue <pii> q;

    q.push({0, root});
    dis[root][o] = 0;

    while (!q.empty()) {
        w = -q.top().fi;
        x = q.top().se;
        q.pop();

        if (dis[x][o] != w) continue;

        for (auto e : veze[x]) {
            y = e.fi;
            w2 = w + e.se;

            if (dis[y][o] != -1 && dis[y][o] <= w2) continue;

            dis[y][o] = w2;
            q.push({-w2, y});
        }
    }
}

void bfs(ll root, int o) {
    priority_queue <pii> q;

    q.push({0, root});
    arr[root][o] = 0;

    while (!q.empty()) {
        w = -q.top().fi;
        x = q.top().se;
        q.pop();

        if (arr[x][o] != w) continue;

        for (auto e : veze[x]) {
            y = e.fi;
            w2 = w + e.se;

            if (arr[y][o] != -1 && arr[y][o] <= w2) continue;

            arr[y][o] = w2;
            q.push({-w2, y});
        }
    }
}

void tramvaj(ll root, int o) {
    queue <ll> q;

    q.push(root);
    trm[root][o] = 1;

    while (!q.empty()) {
        x = q.front();
        q.pop();

        for (auto e : veze[x]) {
            if (arr[e.fi][o] + e.se != arr[x][o]) continue;
            if (trm[e.fi][o]) continue;

            trm[e.fi][o] = 1;
            q.push(e.fi);
        }
    }
}

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

    cin >> n >> m;
    cin >> s >> t >> u >> v;

    memset(dis, -1, sizeof(dis));
    memset(arr, -1, sizeof(arr));

    for (ll i = 0; i < m; i++) {
        cin >> x >> y >> w;

        veze[x].push_back({y, w});
        veze[y].push_back({x, w});
    }

    distance(u, 0);
    distance(v, 1);

    bfs(s, 0);
    bfs(t, 1);

    tramvaj(t, 0);
    tramvaj(s, 1);

    ll rez = 1e18;
    for (int i = 0; i < 2; i++) {
        for (ll j = 1; j <= n; j++) {
            if (!trm[j][i]) continue;

            sol[j][0] = dis[j][0];
            sol[j][1] = dis[j][1];
        }

        for (int j = 1; j <= n; j++) q.push({-sol[j][0], j});

        while (!q.empty()) {
            w = -q.top().fi;
            x = q.top().se;
            q.pop();

            if (w != sol[x][0]) continue;

            for (auto e : veze[x]) {
                if (!trm[e.fi][i]) continue;
                if (arr[e.fi][i] != arr[x][i] + e.se) continue;
                if (sol[x][0] >= sol[e.fi][0]) continue;

                sol[e.fi][0] = sol[x][0];
                q.push({sol[e.fi][0], e.fi});
            }
        }

        for (int j = 1; j <= n; j++) q.push({-sol[j][1], j});
        while (!q.empty()) {
            w = -q.top().fi;
            x = q.top().se;
            q.pop();

            if (w != sol[x][1]) continue;

            for (auto e : veze[x]) {
                if (!trm[e.fi][i]) continue;
                if (arr[e.fi][1 - i] != arr[x][1 - i] + e.se) continue;
                if (sol[x][1] >= sol[e.fi][1]) continue;

                sol[e.fi][1] = sol[x][1];
                q.push({sol[e.fi][1], e.fi});
            }
        }

//        cout << rez << " || ";
        rez = min(rez, dis[v][0]);
//        cout << rez << " || ";
        for (ll j = 1; j <= n; j++) {
            if (!trm[j][i]) continue;

//            cout << j << " j " << sol[j][0] + sol[j][1] << " | ";
//
            rez = min(rez, sol[j][0] + sol[j][1]);
//            cout << rez << " | ";
        }
//        cout << "\n";


//        cout << "___________________________________________\n";
//        cout << rez << "\n";
//
//        cout << "U dis[" << u << "] = "; for (ll j = 1; j <= n; j++) cout << dis[j][0] << " "; cout << "\n";
//        cout << "V dis[" << v << "] = "; for (ll j = 1; j <= n; j++) cout << dis[j][1] << " "; cout << "\n";
//        cout << "\n";
//
//        cout << "bfs -> "; for (ll j = 1; j <= n; j++) cout << arr[j][i] << " "; cout << "\n";
//        cout << "trm -> "; for (ll j = 1; j <= n; j++) cout << trm[j][i] << " "; cout << "\n";
//        cout << "\n";
//
//        cout << "0 sol -> "; for (ll j = 1; j <= n; j++) cout << sol[j][0] << " "; cout << "\n";
//        cout << "1 sol -> "; for (ll j = 1; j <= n; j++) cout << sol[j][1] << " "; cout << "\n";
//        cout << "\n";
//
//        cout << "___________________________________________\n";
    }

    cout << rez << "\n";

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 42316 KB Output is correct
2 Correct 360 ms 42204 KB Output is correct
3 Correct 381 ms 42684 KB Output is correct
4 Correct 255 ms 42300 KB Output is correct
5 Correct 332 ms 42124 KB Output is correct
6 Correct 337 ms 42464 KB Output is correct
7 Correct 316 ms 42084 KB Output is correct
8 Correct 311 ms 41984 KB Output is correct
9 Correct 313 ms 41908 KB Output is correct
10 Correct 252 ms 41844 KB Output is correct
11 Correct 148 ms 36036 KB Output is correct
12 Correct 288 ms 41836 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 42156 KB Output is correct
2 Correct 305 ms 42128 KB Output is correct
3 Correct 317 ms 42196 KB Output is correct
4 Correct 330 ms 42100 KB Output is correct
5 Correct 316 ms 42200 KB Output is correct
6 Correct 369 ms 42088 KB Output is correct
7 Correct 331 ms 41932 KB Output is correct
8 Correct 345 ms 42484 KB Output is correct
9 Correct 315 ms 42068 KB Output is correct
10 Correct 326 ms 42180 KB Output is correct
11 Correct 176 ms 35964 KB Output is correct
12 Correct 355 ms 42056 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28248 KB Output is correct
2 Correct 6 ms 26716 KB Output is correct
3 Incorrect 6 ms 26460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 42316 KB Output is correct
2 Correct 360 ms 42204 KB Output is correct
3 Correct 381 ms 42684 KB Output is correct
4 Correct 255 ms 42300 KB Output is correct
5 Correct 332 ms 42124 KB Output is correct
6 Correct 337 ms 42464 KB Output is correct
7 Correct 316 ms 42084 KB Output is correct
8 Correct 311 ms 41984 KB Output is correct
9 Correct 313 ms 41908 KB Output is correct
10 Correct 252 ms 41844 KB Output is correct
11 Correct 148 ms 36036 KB Output is correct
12 Correct 288 ms 41836 KB Output is correct
13 Correct 333 ms 42156 KB Output is correct
14 Correct 305 ms 42128 KB Output is correct
15 Correct 317 ms 42196 KB Output is correct
16 Correct 330 ms 42100 KB Output is correct
17 Correct 316 ms 42200 KB Output is correct
18 Correct 369 ms 42088 KB Output is correct
19 Correct 331 ms 41932 KB Output is correct
20 Correct 345 ms 42484 KB Output is correct
21 Correct 315 ms 42068 KB Output is correct
22 Correct 326 ms 42180 KB Output is correct
23 Correct 176 ms 35964 KB Output is correct
24 Correct 355 ms 42056 KB Output is correct
25 Correct 13 ms 28248 KB Output is correct
26 Correct 6 ms 26716 KB Output is correct
27 Incorrect 6 ms 26460 KB Output isn't correct
28 Halted 0 ms 0 KB -