QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#643855 | #2289. Jail or Joyride | wlz | WA | 34ms | 6820kb | C++20 | 3.3kb | 2024-10-16 03:10:37 | 2024-10-16 03:10: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 && u == t) || (u == p1 && v == t)) && !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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
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: 3668kb
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: 0ms
memory: 3804kb
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: 3572kb
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: 0
Accepted
time: 1ms
memory: 3696kb
input:
4 4 3 2 1 2 1 2 3 10 2 4 5 4 3 6
output:
31
result:
ok single line: '31'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
2 1 2 1 2 1 1
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 34ms
memory: 6620kb
input:
300 44850 247 85 272 228 288849537 241 43 9873162 189 240 10538237 136 291 880425990 91 207 56502487 7 277 568371880 251 9 636070665 166 7 628732259 130 183 203171884 7 12 786299190 285 280 282670657 180 263 699873645 63 207 872780899 271 245 230237525 123 58 404988100 34 217 990722599 259 50 355842...
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
3 2 1 2 2 3 12 1 2 70
output:
82
result:
ok single line: '82'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
3 3 1 3 1 3 1 2 3 1 1 2 1
output:
impossible
result:
ok single line: 'impossible'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
4 4 3 2 3 1 1 3 4 1 2 1 1 2 4 1
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
4 4 2 1 3 1 5 1 4 3 2 1 5 2 4 5
output:
20
result:
ok single line: '20'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
4 4 2 4 3 4 7 4 2 5 1 2 5 3 2 5
output:
15
result:
ok single line: '15'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
4 4 2 3 2 1 10 1 4 9 4 2 2 1 3 3
output:
13
result:
ok single line: '13'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
4 4 3 4 3 2 9 4 2 13 1 2 20 1 4 16
output:
44
result:
ok single line: '44'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
4 4 4 2 4 3 368412026 4 2 248686681 1 3 856765094 3 2 319358821
output:
1424810596
result:
ok single line: '1424810596'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
4 5 3 2 3 1 3 4 2 7 4 3 17 2 3 14 2 1 4
output:
impossible
result:
ok single line: 'impossible'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
4 6 1 2 1 4 1 2 4 1 2 3 1 1 3 1 4 3 1 1 2 1
output:
impossible
result:
ok single line: 'impossible'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
5 5 4 5 1 5 1 3 5 1 2 1 2 3 4 2 2 4 2
output:
impossible
result:
ok single line: 'impossible'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
5 6 3 4 3 4 3 1 5 2 4 2 3 2 3 2 1 4 1 5 3 1
output:
impossible
result:
ok single line: 'impossible'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
5 6 3 2 1 5 10 3 1 8 3 5 6 3 4 7 1 4 6 1 2 6
output:
14
result:
ok single line: '14'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
5 7 5 1 1 2 1 4 2 1 2 5 1 4 3 1 1 4 1 1 5 1 1 3 1
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
5 8 2 1 3 2 218 2 1 176 5 1 177 5 2 248 5 3 249 3 1 110 2 4 24 1 4 269
output:
impossible
result:
ok single line: 'impossible'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
6 6 2 6 4 5 34 4 2 13 6 4 18 3 6 3 1 2 15 1 6 2
output:
69
result:
ok single line: '69'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
6 7 2 4 6 1 5 2 4 3 3 5 5 5 4 2 4 3 1 6 2 5 6 3 6
output:
15
result:
ok single line: '15'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
6 8 3 5 3 5 5 4 1 6 5 2 9 5 1 10 1 6 1 3 2 10 4 6 1 2 6 6
output:
impossible
result:
ok single line: 'impossible'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
7 7 4 2 3 6 1 3 5 1 1 7 1 1 5 1 5 4 1 7 3 1 4 2 1
output:
1
result:
ok single line: '1'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
7 8 6 2 2 5 5 3 2 1 4 6 10 2 6 3 1 2 6 5 3 4 7 4 9 4 2 2
output:
14
result:
ok single line: '14'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
7 10 2 5 4 2 5 5 4 3 2 5 5 1 3 4 1 6 7 1 5 6 3 7 1 6 4 6 5 3 6 7 1 3
output:
impossible
result:
ok single line: 'impossible'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
7 10 5 2 3 6 39 7 2 38 1 3 5 2 3 38 4 2 8 1 4 26 5 6 9 2 6 12 7 5 10 5 2 20
output:
impossible
result:
ok single line: 'impossible'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
10 20 7 4 5 1 326 2 3 264 10 4 132 5 3 279 5 8 215 7 10 161 3 6 51 4 9 184 5 10 183 8 1 26 7 3 27 4 5 215 6 8 8 8 7 166 4 3 272 8 9 176 1 9 336 7 2 276 9 10 190 2 1 239
output:
impossible
result:
ok single line: 'impossible'
Test #31:
score: 0
Accepted
time: 14ms
memory: 4324kb
input:
300 1000 172 215 188 170 616047457 52 84 278955639 40 242 753349504 163 138 601228798 161 16 632160688 179 229 448530394 69 143 427101036 289 245 202138801 196 67 997170084 39 117 521910244 280 119 344655702 79 105 274646714 241 183 674512683 113 66 937810400 273 93 112339663 3 233 976547617 250 290...
output:
5348814077
result:
ok single line: '5348814077'
Test #32:
score: 0
Accepted
time: 18ms
memory: 4440kb
input:
300 1100 100 209 234 247 129576659 223 207 495744462 250 245 370280902 236 223 325806963 21 168 236892887 142 294 269589834 57 268 228614730 224 272 564986018 144 180 789479441 80 223 596750678 191 71 160344159 47 216 372222097 21 213 688891280 266 19 86672638 224 291 121388362 46 267 782845752 144 ...
output:
impossible
result:
ok single line: 'impossible'
Test #33:
score: 0
Accepted
time: 18ms
memory: 4652kb
input:
300 1200 280 270 290 215 142763387 265 6 456937853 97 2 443824682 137 282 20821198 160 24 657412199 111 286 318196770 68 21 428221756 31 42 810534537 13 203 222659805 239 35 473326669 185 263 811450004 184 51 970813488 184 129 117775566 207 257 961208198 90 273 889191275 195 92 688431433 225 289 799...
output:
impossible
result:
ok single line: 'impossible'
Test #34:
score: 0
Accepted
time: 19ms
memory: 4496kb
input:
300 1300 146 220 208 279 648697459 177 81 569984532 271 172 75673577 111 87 823942494 114 221 93895642 28 13 610640568 123 49 675046234 7 11 814261068 6 112 849880821 44 102 191765378 194 71 458986251 44 299 40639500 222 203 552484031 281 54 904738800 262 1 117666457 218 285 597332137 178 274 262492...
output:
4499816248
result:
ok single line: '4499816248'
Test #35:
score: 0
Accepted
time: 19ms
memory: 6820kb
input:
300 44552 287 269 227 115 548036515 93 91 628350792 250 252 502289063 97 209 534358326 110 241 768940017 98 40 583581799 216 214 774195697 155 176 665236097 208 234 506173664 173 191 563654096 56 251 649853757 76 158 552516897 118 217 638728245 24 208 585001158 47 53 511152597 119 4 595679501 252 10...
output:
227123159923
result:
ok single line: '227123159923'
Test #36:
score: 0
Accepted
time: 22ms
memory: 6544kb
input:
300 44552 286 4 5 230 519205384 75 243 594662040 171 143 601575881 105 258 537465083 254 269 515988676 246 236 551981769 26 103 660351971 89 62 527015047 162 227 657894482 59 140 557606029 276 207 578075434 40 81 562127352 210 227 551822641 282 198 559798359 198 206 697959211 11 285 504393704 201 74...
output:
224960401788
result:
ok single line: '224960401788'
Test #37:
score: 0
Accepted
time: 26ms
memory: 6772kb
input:
300 44552 197 57 81 259 752534769 79 203 509657942 170 11 502931716 58 265 694687977 259 55 792380133 236 180 525303065 126 123 518209783 69 197 693391526 31 221 747245032 29 46 502292752 13 29 517712948 231 150 506527443 176 9 586627034 29 257 518509117 81 291 501256348 124 49 538508861 21 153 7296...
output:
impossible
result:
ok single line: 'impossible'
Test #38:
score: 0
Accepted
time: 23ms
memory: 6716kb
input:
300 44552 40 295 103 162 591922054 250 11 564950165 73 25 580398032 104 190 736154443 272 45 503437248 41 85 512700615 90 112 749845628 218 138 886819302 61 187 577547406 291 294 501904049 206 168 591336383 261 44 587686409 220 136 560833391 229 125 520593741 289 47 702058631 174 73 860700506 166 87...
output:
impossible
result:
ok single line: 'impossible'
Test #39:
score: 0
Accepted
time: 27ms
memory: 6724kb
input:
300 39080 42 278 291 159 427963580 204 294 937650102 281 67 345788850 260 138 714423802 219 183 791077534 105 270 275364519 90 161 485996114 83 137 534334841 183 40 577892370 55 56 944642483 174 116 967635210 4 78 555949032 291 293 204023674 8 45 197737396 121 73 581306709 69 138 595251478 30 257 99...
output:
impossible
result:
ok single line: 'impossible'
Test #40:
score: 0
Accepted
time: 26ms
memory: 6628kb
input:
300 39080 9 197 290 60 66163289 34 243 521539706 238 65 517914138 14 148 798485355 277 118 870931863 18 285 306051313 15 150 784036092 142 108 535170265 72 135 591196449 233 254 397144380 72 225 805611789 256 115 723310929 148 214 950528407 49 275 468427236 105 214 92222696 213 227 633472321 156 144...
output:
383739292
result:
ok single line: '383739292'
Test #41:
score: 0
Accepted
time: 31ms
memory: 6556kb
input:
300 39080 18 203 146 276 67533670 168 85 316545590 277 118 326013895 159 192 62119183 1 87 96284866 51 3 779788450 95 18 172323983 262 49 818221800 131 68 971895870 130 196 287909172 16 227 715603810 44 128 488234620 134 214 702351838 280 16 381668858 226 83 119997136 223 242 391933081 30 257 435633...
output:
106867015
result:
ok single line: '106867015'
Test #42:
score: 0
Accepted
time: 27ms
memory: 6748kb
input:
300 44552 149 84 278 112 718471406 91 167 518128774 230 239 791658366 125 36 537442283 64 71 515587338 30 243 727716216 191 151 569453594 117 57 545718345 255 247 694574358 269 30 689527019 148 35 591433196 260 203 526609974 170 91 589172304 11 204 747570818 124 171 633673849 73 251 573282708 286 26...
output:
impossible
result:
ok single line: 'impossible'
Test #43:
score: 0
Accepted
time: 23ms
memory: 6716kb
input:
300 44552 254 41 4 141 554293422 20 48 534967985 190 287 690822382 175 65 614458874 111 20 699846518 177 169 651888000 25 230 816778486 279 91 535636398 4 37 518939471 44 199 547415294 167 135 640363956 1 144 512874962 22 280 793080602 56 258 540070776 66 75 907078252 274 289 695554943 119 233 75870...
output:
impossible
result:
ok single line: 'impossible'
Test #44:
score: -100
Wrong Answer
time: 26ms
memory: 6776kb
input:
300 44552 222 238 156 258 631488958 63 207 886014070 25 200 780019280 209 28 603960920 143 197 620131672 31 56 547633072 270 250 647577852 36 193 592004078 223 70 718374970 24 185 769138438 88 180 685018826 287 277 691048950 3 235 946084034 199 81 612462230 11 255 538906282 78 90 732934274 8 234 578...
output:
8998963606
result:
wrong answer 1st lines differ - expected: '209586637319', found: '8998963606'