QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122547#2289. Jail or Joyridebatrr#AC ✓121ms5212kbC++173.8kb2023-07-10 18:49:412023-07-10 18:49:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 18:49:57]
  • 评测
  • 测评结果:AC
  • 用时:121ms
  • 内存:5212kb
  • [2023-07-10 18:49:41]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 305, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int n, m, S, T;

ll d[N][N], dd[N][N];
ll dp[N], d_mx[N];


bool good[N];

vector<int> g[N];

int p[N];

int pp(int v) {
    return p[v] == v ? v : p[v] = pp(p[v]);
}

int col[N];

void dfs(int v) {
    if (col[v] == 1) {
        dp[v] = INF;
        return;
    }
    if (col[v] == 2)
        return;
    col[v] = 1;
    dp[v] = 0;
    if (!good[v]) {
        for (auto to: g[v]) {
            dfs(to);
            dp[v] = max(dp[v], dp[to] + d_mx[v]);
        }
    }
    col[v] = 2;
}

void solve() {
    cin >> n >> m;
    cin >> S >> T;
    S--, T--;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = INF;

    for (int i = 0; i < m; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        v--, u--;
        d[v][u] = d[u][v] = w;
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dd[i][j] = d[i][j];

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]);

    for (int v = 0; v < n; v++) {
        d_mx[v] = -INF;
        for (int u = 0; u < n; u++)
            if (v != u && dd[v][u] < INF)
                d_mx[v] = max(d_mx[v], dd[v][u]);
        for (int u = 0; u < n; u++)
            if (v != u && dd[v][u] == d_mx[v]) {
//                cerr << v << " " << u << " " << d_mx[v] << endl;
                g[v].pb(u);
            }

        int cnt = 0;
        for (int u = 0; u < n; u++)
            if (v != u && d[v][u] < INF)
                cnt++;
        if (cnt == 1)
            good[v] = 1;
    }
    set<pll> st;
    for (int v = 0; v < n; v++) {
        if (good[v])
            dp[v] = 0;
        else
            dp[v] = INF;
        st.insert({dp[v], v});
    }

    if (good[T]) {
        cout << dd[S][T] << "\n";
        return;
    }

    int bridge = -1;
    for (int i = 0; i < n; i++) {
        iota(p, p + n, 0);
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                if (d[a][b] == INF)
                    continue;
                if (a == i && b == T)
                    continue;
                if (a == T && b == i)
                    continue;
                p[pp(a)] = pp(b);
            }
        }
        if (pp(T) != pp(S)) {
            bridge = i;
            break;
        }
    }
    iota(p, p + n, 0);
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            if (d[a][b] == INF)
                continue;
            if (a == bridge && b == T)
                continue;
            if (a == T && b == bridge)
                continue;
            p[pp(a)] = pp(b);
        }
    }
    vector<int> starts;
    ll mx = -INF;
    for (int u = 0; u < n; u++)
        if (T != u && dd[T][u] < INF && pp(T) == pp(u))
            mx = max(mx, dd[T][u]);
    for (int u = 0; u < n; u++)
        if (T != u && dd[T][u] == mx && pp(T) == pp(u))
            starts.pb(u);

    ll ans = -INF;

    for (auto v: starts) {
        dfs(v);
        ans = max(ans, dp[v]);
    }
    if (ans >= INF) {
        cout << "impossible\n";
        return;
    }
    cout << ans + dd[S][T] + mx << "\n";
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

详细

Test #1:

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

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: 0ms
memory: 3512kb

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: 3532kb

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: 3556kb

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: 3548kb

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: 3524kb

input:

2 1 2 1
2 1 1

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 106ms
memory: 4960kb

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: 0ms
memory: 3540kb

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: 3444kb

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: 0ms
memory: 3512kb

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: 3444kb

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: 0ms
memory: 3520kb

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: 3516kb

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: 0ms
memory: 3488kb

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: 0ms
memory: 3492kb

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: 3508kb

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: 3440kb

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: 3452kb

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: 3448kb

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: 3444kb

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: 3456kb

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: 3496kb

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: 3544kb

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: 3452kb

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: 1ms
memory: 3448kb

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: 3504kb

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: 2ms
memory: 3524kb

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: 3460kb

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: 3460kb

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: 3560kb

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: 36ms
memory: 4884kb

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: 33ms
memory: 4920kb

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: 38ms
memory: 4896kb

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: 35ms
memory: 4940kb

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: 112ms
memory: 4968kb

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: 110ms
memory: 4980kb

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: 121ms
memory: 5008kb

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: 111ms
memory: 4980kb

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: 101ms
memory: 4896kb

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: 96ms
memory: 4956kb

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: 96ms
memory: 4936kb

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: 106ms
memory: 4996kb

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: 104ms
memory: 5052kb

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: 0
Accepted
time: 111ms
memory: 5168kb

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:

209586637319

result:

ok single line: '209586637319'

Test #45:

score: 0
Accepted
time: 112ms
memory: 5184kb

input:

300 44552 145 38
216 16 47135
148 192 67900
1 160 49668
93 204 50724
8 61 47340
250 2 53176
83 194 84926
205 179 80156
217 225 78718
43 26 57672
161 121 51829
166 168 59786
235 193 73904
212 282 82242
241 4 46654
181 128 64002
194 183 73276
42 154 48000
171 244 49030
275 281 82680
119 207 85490
134 ...

output:

19171281

result:

ok single line: '19171281'

Test #46:

score: 0
Accepted
time: 111ms
memory: 5120kb

input:

300 44552 213 298
255 141 95756
80 283 78536
215 220 75950
161 286 92270
34 199 109054
183 67 73788
45 278 69298
11 123 65798
250 81 81590
279 96 82708
73 246 83538
83 96 67058
2 86 114094
86 162 117148
188 70 79520
131 237 69144
245 58 72806
10 125 100910
203 76 68016
158 255 62062
228 234 99026
12...

output:

27074835

result:

ok single line: '27074835'

Test #47:

score: 0
Accepted
time: 111ms
memory: 5196kb

input:

300 44552 219 40
50 14 6736278
248 78 8209274
132 232 7611628
290 21 9023104
152 232 11471044
195 168 8311390
233 49 6940578
38 295 9917502
165 228 6802724
108 9 6810476
87 239 7105610
221 21 9023104
35 139 8754520
71 42 6387636
222 133 6346460
270 152 6814568
132 180 7611628
116 14 6990440
123 215 ...

output:

2768983979

result:

ok single line: '2768983979'

Test #48:

score: 0
Accepted
time: 111ms
memory: 5212kb

input:

300 44552 223 19
213 209 508558584
225 208 580483196
241 10 543184464
98 207 528712850
300 5 759305640
139 155 681188442
268 207 504424066
280 152 748833584
186 44 579279968
61 146 872409306
252 231 794578172
281 170 559082128
148 2 716063836
190 19 502567708
244 20 628273788
184 155 717250282
38 10...

output:

226129144133

result:

ok single line: '226129144133'

Test #49:

score: 0
Accepted
time: 32ms
memory: 4936kb

input:

300 549 250 136
161 226 302754920
25 299 744292718
2 129 585942164
227 55 630080037
223 264 652638770
80 74 945166846
260 283 556275323
31 292 335570208
94 218 458760654
110 244 22324959
240 63 333406555
300 8 885373942
88 241 839349887
285 243 85240741
27 61 823814499
213 103 481357820
89 191 80600...

output:

impossible

result:

ok single line: 'impossible'

Test #50:

score: 0
Accepted
time: 32ms
memory: 4996kb

input:

300 552 172 129
227 254 656564987
245 80 930731427
132 93 234529743
124 287 929333178
119 152 177765970
104 60 234122245
227 244 978084068
51 143 527589838
189 30 839829259
199 32 850274115
1 192 175973966
208 69 187650020
174 241 470475812
268 29 517490959
272 289 926588745
115 137 784446351
112 95...

output:

impossible

result:

ok single line: 'impossible'

Test #51:

score: 0
Accepted
time: 32ms
memory: 4896kb

input:

300 572 159 67
70 92 636545482
95 47 846418054
85 159 13005960
165 224 13241434
218 263 698421178
113 186 105144666
91 117 108649363
38 257 468163544
62 50 294487485
164 252 147518448
278 61 568258282
257 279 384366500
214 109 44680761
226 123 312409288
73 100 309131012
226 205 711136909
136 103 642...

output:

impossible

result:

ok single line: 'impossible'

Test #52:

score: 0
Accepted
time: 32ms
memory: 4980kb

input:

300 574 235 191
23 58 404529967
270 42 295539930
118 71 753240041
97 299 387427389
292 156 389043904
132 18 455839190
283 293 907558745
152 171 83158533
279 126 360938362
58 103 970012732
226 141 752604290
156 151 190530500
252 37 795421863
223 228 389469597
35 77 425778243
295 77 278030420
33 284 1...

output:

impossible

result:

ok single line: 'impossible'

Test #53:

score: 0
Accepted
time: 28ms
memory: 4928kb

input:

300 591 96 9
210 86 590114463
267 242 751398898
277 1 484819944
140 48 598267863
20 227 700870703
168 142 47048811
16 162 862680294
237 5 640989403
142 182 224336238
221 182 769399107
199 84 741577948
251 124 825504334
19 127 859776391
290 14 425281959
174 142 377631381
207 132 997911070
139 43 4260...

output:

impossible

result:

ok single line: 'impossible'

Test #54:

score: 0
Accepted
time: 32ms
memory: 4932kb

input:

300 590 9 291
286 20 364525047
173 62 175790536
227 281 504952895
54 285 41076815
246 281 36678112
116 120 72095500
33 55 536651913
252 23 204904130
114 64 421648793
123 39 379864697
83 45 991207123
291 74 878139894
71 115 625358539
120 233 149800095
157 238 796152306
293 95 683103454
221 202 859077...

output:

8826805205

result:

ok single line: '8826805205'

Test #55:

score: 0
Accepted
time: 27ms
memory: 4972kb

input:

300 300 1 150
150 151 999999703
299 1 1000000000
149 150 999999849
298 299 999999847
148 149 999999845
297 298 999999843
147 148 999999841
296 297 999999839
146 147 999999837
295 296 999999835
145 146 999999833
294 295 999999831
144 145 999999829
293 294 999999827
143 144 999999825
292 293 999999823...

output:

44550980174805

result:

ok single line: '44550980174805'

Test #56:

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

input:

9 10 4 2
1 5 2
2 9 1
2 3 1
3 6 2
9 5 1
8 7 2
9 1 1
3 8 1
1 4 2
3 7 3

output:

16

result:

ok single line: '16'

Test #57:

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

input:

13 12 5 9
3 10 9
9 12 4
12 6 1
8 4 1
3 5 9
9 7 1
2 10 4
7 11 7
7 1 7
12 8 2
13 11 2
9 2 6

output:

38

result:

ok single line: '38'

Test #58:

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

input:

13 18 12 13
5 11 9
11 9 1
10 12 9
5 6 11
13 5 9
11 6 3
6 9 2
2 4 8
1 3 10
13 1 6
2 10 2
1 7 4
2 12 3
4 10 4
1 8 2
13 2 6
3 7 11
3 8 10

output:

impossible

result:

ok single line: 'impossible'

Test #59:

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

input:

11 10 11 2
2 1 6
5 10 7
6 7 3
1 4 6
9 11 15
2 6 20
2 5 2
2 3 17
3 8 4
2 9 1

output:

39

result:

ok single line: '39'

Test #60:

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

input:

26 41 3 15
11 25 1516
25 2 13643
6 26 22956
24 3 3199
26 13 3123
25 7 693
18 4 7063
17 12 4249
9 5 6906
6 10 15094
23 1 14632
9 7 21641
22 19 10142
21 18 17965
22 20 15472
23 10 8440
5 18 15071
8 13 3097
3 8 6577
21 7 18839
16 19 20
8 10 13213
24 7 14025
26 14 16201
26 11 9598
24 23 5893
20 1 4586
5...

output:

34414

result:

ok single line: '34414'

Test #61:

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

input:

25 32 1 20
7 12 1
9 2 1
13 5 1
19 11 1
20 1 1
10 5 1
20 22 1
20 13 1
20 6 1
14 5 1
5 21 1
1 25 1
18 25 1
17 15 1
6 19 1
3 14 1
22 9 1
22 2 1
7 23 1
6 11 1
6 12 1
14 21 1
10 21 1
17 2 1
24 25 1
7 19 1
18 8 1
17 4 1
1 16 1
22 4 1
16 25 1
18 16 1

output:

5

result:

ok single line: '5'

Test #62:

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

input:

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

output:

8

result:

ok single line: '8'

Test #63:

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

input:

29 35 3 21
21 10 2
13 15 2
21 4 2
13 26 2
27 16 2
29 1 1
19 20 1
12 20 1
18 7 2
10 25 2
21 13 1
17 11 2
22 18 1
4 27 2
19 12 1
28 29 1
21 28 2
21 17 1
10 5 1
23 7 2
13 2 1
28 24 1
14 11 1
10 8 2
15 26 2
21 23 2
5 25 1
23 18 2
19 3 1
6 27 1
21 19 1
4 6 2
17 9 2
9 11 1
28 1 2

output:

8

result:

ok single line: '8'

Test #64:

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

input:

9 12 8 5
2 3 14
2 1 30
8 4 34
5 2 7
1 6 18
1 3 11
9 4 15
8 9 41
5 8 45
2 6 10
9 7 27
4 7 24

output:

impossible

result:

ok single line: 'impossible'

Test #65:

score: 0
Accepted
time: 16ms
memory: 4904kb

input:

291 860 245 101
93 240 139120977
4 105 465159603
176 50 492215454
273 189 483639200
157 116 232931924
32 141 92675667
255 164 841735017
227 230 164114236
153 158 707815296
158 286 905114861
152 93 328668329
91 248 639218718
120 80 969611333
41 45 348194315
163 109 842362396
91 15 975452666
11 170 57...

output:

2778746641

result:

ok single line: '2778746641'

Test #66:

score: 0
Accepted
time: 20ms
memory: 4948kb

input:

298 753 7 80
22 15 655688600
81 163 469418355
211 271 389494406
267 253 43248012
267 297 901272832
275 44 772567220
268 47 497467394
65 131 172141554
122 168 537882203
31 36 146328360
18 180 250286555
98 82 961319091
36 157 857542084
39 30 959430984
85 2 525765555
18 21 53055902
61 129 304562301
8 2...

output:

4530081357

result:

ok single line: '4530081357'

Test #67:

score: 0
Accepted
time: 20ms
memory: 4952kb

input:

299 702 196 246
277 183 651503196
216 143 908339786
280 176 643089047
145 29 412457391
150 3 414127417
207 217 969216638
168 129 84624326
45 237 720719430
242 47 856554750
282 19 175746571
62 134 313783712
169 294 817648372
175 86 764676949
126 191 83022901
75 234 946103174
155 131 261182820
59 201 ...

output:

4659963895

result:

ok single line: '4659963895'