QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643850 | #2289. Jail or Joyride | wlz | WA | 1ms | 3784kb | C++20 | 3.2kb | 2024-10-16 02:59:38 | 2024-10-16 02:59:39 |
Judging History
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'