oj.uz

답안 #959195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959195 2024-04-07T16:00:11 Z vjudge1 Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 673 ms 55704 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E5+16, INF = ll(1E18)+16;
vector <pair <ll, ll> > adj[4*MAXN];
ll dis[4*MAXN];
bool vis[4*MAXN];

ll enc (ll u, int graphid) { return ((u<<2)|graphid); } // encode state into number
ll unenc (ll u) { return (u>>2); } // unencode
// graphid:
// 0b00 regular level 0 graph
// 0b01 foward dijkstra dag from u1 to v1 (commuter pass) level 1 graph
// 0b10 reverse dijkstra dag, same as 0b01 (commuter pass) level 1 graph
// 0b11 regular graph, same as 0b00, level 2 graph

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    ll u1, v1, u2, v2;
    cin >> u1 >> v1 >> u2 >> v2;
    u1--; v1--; u2--; v2--;
    auto addEdge = [&](ll u, ll v, ll w) { adj[u].push_back({ v, w }); };
    for (ll i = 0; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        addEdge(enc(u, 0b00), enc(v, 0b00), w); // reg graph 1 (0b00)
        addEdge(enc(v, 0b00), enc(u, 0b00), w);
        addEdge(enc(u, 0b11), enc(v, 0b11), w); // reg graph 2 (0b11)
        addEdge(enc(v, 0b11), enc(u, 0b11), w);
    }
    {priority_queue <pair <ll, ll> > pq;
    for (ll i = 0; i < 4*MAXN; i++) dis[i] = INF;
    for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
    dis[enc(u1, 0b00)] = 0;
    pq.push({ -dis[enc(u1, 0b00)], enc(u1, 0b00) });
    while (pq.size()) {
        ll u = pq.top().second; pq.pop();
        if (u == enc(v2, 0b00)) break;
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dis[v] <= dis[u]+w) continue;
            dis[v] = dis[u]+w;
            pq.push({ -dis[v], v });
        }
    }
    for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
    function <void(ll)> dfs = [&](ll u) {
        if (vis[u]) return;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dis[v]+w != dis[u]) continue;
            cerr << unenc(v)+1 << ' ' << unenc(u)+1 << '\n';
            addEdge(enc(unenc(v), 0b01), enc(unenc(u), 0b01), 0); // dag fow (0b01)
            addEdge(enc(unenc(u), 0b10), enc(unenc(v), 0b10), 0); // dag rev (0b10)
            dfs(v);
        }
    };
    dfs(enc(v1, 0b00));}
    for (ll u = 0; u < n; u++) { // transitions between graphs
        addEdge(enc(u, 0b00), enc(u, 0b01), 0); // 0b00 to dag fow (0b01)
        addEdge(enc(u, 0b00), enc(u, 0b10), 0); // 0b00 to dag rev (0b10)
        addEdge(enc(u, 0b01), enc(u, 0b11), 0); // 0b01 to reg graph 2 (0b11)
        addEdge(enc(u, 0b10), enc(u, 0b11), 0); // 0b10 to reg graph 2 (0b11)
    }
    {priority_queue <pair <ll, ll> > pq;
    for (ll i = 0; i < 4*MAXN; i++) dis[i] = INF;
    for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
    dis[enc(u2, 0b00)] = 0;
    pq.push({ -dis[enc(u2, 0b00)], enc(u2, 0b00) });
    while (pq.size()) {
        ll u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dis[v] <= dis[u]+w) continue;
            dis[v] = dis[u]+w;
            pq.push({ -dis[v], v });
        }
    }
    cout << dis[enc(v2, 0b11)] << '\n';}
    return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 54012 KB Output is correct
2 Correct 565 ms 51728 KB Output is correct
3 Correct 370 ms 50728 KB Output is correct
4 Correct 355 ms 50684 KB Output is correct
5 Correct 673 ms 53212 KB Output is correct
6 Correct 396 ms 55704 KB Output is correct
7 Incorrect 380 ms 51256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 393 ms 51936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 16720 KB Output is correct
2 Correct 4 ms 13400 KB Output is correct
3 Incorrect 4 ms 13404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 54012 KB Output is correct
2 Correct 565 ms 51728 KB Output is correct
3 Correct 370 ms 50728 KB Output is correct
4 Correct 355 ms 50684 KB Output is correct
5 Correct 673 ms 53212 KB Output is correct
6 Correct 396 ms 55704 KB Output is correct
7 Incorrect 380 ms 51256 KB Output isn't correct
8 Halted 0 ms 0 KB -