QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643855#2289. Jail or JoyridewlzWA 34ms6820kbC++203.3kb2024-10-16 03:10:372024-10-16 03:10:39

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 03:10:39]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:6820kb
  • [2024-10-16 03:10:37]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'