QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643850#2289. Jail or JoyridewlzWA 1ms3784kbC++203.2kb2024-10-16 02:59:382024-10-16 02:59:39

Judging History

This is the latest submission verdict.

  • [2024-10-16 02:59:39]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3784kb
  • [2024-10-16 02:59:38]
  • Submitted

answer

#ifndef DEBUG
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<pii>;

template<class T> inline bool cmax(T &a, const T &b)
{ return a < b ? a = b, 1 : 0; }
template<class T> inline bool cmin(T &a, const T &b)
{ return b < a ? a = b, 1 : 0; }

const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, m, p, t;
    cin >> n >> m >> p >> t;

    vector< vector< pair<int, ll> > > g(n + 1);
    vector<vll> dist(n + 1, vll(n + 1, linf));
    rep(i, 1, n + 1) {
        dist[i][i] = 0;
    }
    rep(i, 0, m) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].eb(v, w);
        g[v].eb(u, w);
        dist[u][v] = dist[v][u] = w;
    }

    rep(k, 1, n + 1) {
        rep(i, 1, n + 1) {
            rep(j, 1, n + 1) {
                cmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    vector<vi> far(n + 1);
    rep(i, 1, n + 1) {
        far[i] = {1};
        rep(j, 2, n + 1) {
            if (dist[i][j] > dist[i][far[i][0]]) {
                far[i] = {j};
            } else if (dist[i][j] == dist[i][far[i][0]]) {
                far[i].pb(j);
            }
        }
    }
    debug(far);

    int p1 = -1;
    for (auto &[u, _] : g[t]) {
        if (dist[p][t] == dist[p][u] + dist[u][t]) {
            p1 = u;
        }
    }

    vi reach(n + 1, 0);
    auto dfs = [&](auto &&self, int u) -> void {
        reach[u] = 1;
        for (auto &[v, _] : g[u]) {
            if (v != p1 && !reach[v]) {
                self(self, v);
            }
        }
    };
    dfs(dfs, t);
    
    ll md = -linf;
    vi t1;
    rep(i, 1, n + 1) {
        if (!reach[i]) {
            continue;
        }
        if (dist[t][i] > md) {
            md = dist[t][i];
            t1 = {i};
        } else if (dist[t][i] == md) {
            t1.pb(i);
        }
    }

    ll ans = dist[p][t];
    for (auto &i : t1) {
        vi was(n + 1, 0);
        auto dfs2 = [&](auto &&self, int u) -> ll {
            if (sz(g[u]) == 1) {
                return 0;
            }
            was[u] = 1;
            ll mx = 0;
            for (auto &v : far[u]) {
                if (was[v] == 0) {
                    cmax(mx, dist[u][v] + self(self, v));
                } else if (was[v] == 1) {
                    return linf;
                }
            }
            was[u] = 2;
            return mx;
        };

        cmax(ans, dfs2(dfs2, i) + dist[p][t] + dist[t][i]);
        
    }

    if (ans > ll(1e17)) {
        cout << "impossible\n";
    } else {
        cout << ans << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

9 10 1 2
1 2 225869
2 3 1772
3 4 314393
4 5 692250
5 6 684107
4 6 532792
3 7 441133
7 8 468183
8 9 186297
7 9 228792

output:

impossible

result:

ok single line: 'impossible'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

9 10 3 2
1 2 225869
2 3 1772
3 4 314393
4 5 692250
5 6 684107
4 6 532792
3 7 441133
7 8 468183
8 9 186297
7 9 228792

output:

227641

result:

ok single line: '227641'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

8 22 8 1
1 2 11
1 3 11
1 4 11
1 5 11
1 6 11
1 7 10
2 3 12
2 4 12
2 5 12
2 6 12
2 7 11
3 4 13
3 5 13
3 6 13
3 7 12
4 5 14
4 6 14
4 7 13
5 6 15
5 7 14
6 7 15
7 8 1

output:

92

result:

ok single line: '92'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

6 7 3 6
1 3 2642
3 4 1253
2 4 64316
2 5 235162
6 5 2341
5 3 23
5 4 589201

output:

2364

result:

ok single line: '2364'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3592kb

input:

4 4 3 2
1 2 1
2 3 10
2 4 5
4 3 6

output:

32

result:

wrong answer 1st lines differ - expected: '31', found: '32'