QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113239#2501. Olympic Buslmeowdn100 ✓82ms14268kbC++143.1kb2023-06-16 19:01:482023-06-16 19:01:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 19:01:51]
  • 评测
  • 测评结果：100
  • 用时：82ms
  • 内存：14268kb
查看
  • [2023-06-16 19:01:48]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=5e4+5,inf=0x3f3f3f3f3f3f3f;
int n,m,s,t,dst,dts,dsu[N],dut[N],dtu[N],dus[N],w[N],c[N],pst[N],pts[N],tag[N],ans,vst[205][205];
vp e[N],r[N],g[N];

int dijkstra(int *d,vp *e,int s,int t,int del=0) {
  static bool vst[N]; rep(i,1,n) vst[i]=0;
  rep(i,0,n) d[i]=inf; d[s]=0;
  rep(i,1,n) {
    int u=0;
    rep(j,1,n) if(!vst[j]&&d[j]<d[u]) u=j;
    vst[u]=1;
    for(auto [v,id]:e[u]) if(id!=del)
      d[v]=min(d[v],d[u]+w[id]);
  }
  return d[t];
}
void dfs(int u,int *vst,int del) {
  if(u==del) return; vst[u]=1;
  for(auto [v,id]:g[u]) if(!vst[v]) dfs(v,vst,del);
}
void topo(int s,int *d) {
  rep(i,1,n) rep(j,1,n) vst[i][j]=0;
  rep(i,1,n) dfs(s,vst[i],i);
  rep(u,1,n) for(auto [v,id]:g[u])
    if(d[v]<inf&&!vst[u][v]) tag[id]=1;
}

signed main() {
  n=read(), m=read(), s=1, t=n;
  rep(i,1,m) {
    int u=read(), v=read();
    e[u].eb(v,i), r[v].eb(u,i);
    w[i]=read(), c[i]=read();
  }
  rep(i,1,m) pst[i]=pts[i]=-1;
  dijkstra(dsu,e,s,t), dijkstra(dtu,e,t,s);
  dst=dsu[t], dts=dtu[s];
  rep(u,1,n) for(auto [v,id]:e[u])
    if(dsu[v]==dsu[u]+w[id]) g[u].eb(v,id);
  topo(s,dsu);
  rep(u,1,n) for(auto [v,id]:e[u])
    if(tag[id]) pst[id]=dijkstra(dsu,e,s,t,id);
  rep(i,1,n) g[i].clear();
  rep(i,1,m) tag[i]=0;
  rep(u,1,n) for(auto [v,id]:e[u])
    if(dtu[v]==dtu[u]+w[id]) g[u].eb(v,id);
  topo(t,dtu);
  rep(u,1,n) for(auto [v,id]:e[u])
    if(tag[id]) pts[id]=dijkstra(dtu,e,t,s,id);
  dijkstra(dsu,e,s,t), dijkstra(dut,r,t,s);
  dijkstra(dtu,e,t,s), dijkstra(dus,r,s,t);
  ans=dst+dts;
  rep(u,1,n) for(auto [v,id]:e[u]) {
    int res=c[id];
    if(~pst[id]) res+=pst[id];
    else res+=min(dst,dsu[v]+w[id]+dut[u]);
    if(~pts[id]) res+=pts[id];
    else res+=min(dts,dtu[v]+w[id]+dus[u]);
    ans=min(ans,res);
  }
  if(ans>=inf) puts("-1");
  else printf("%lld\n",ans);
  return 0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 5ms
memory: 10900kb

input:

200 1000
122 152 0 182437847
22 126 0 800796216
142 158 0 932784437
27 61 0 220600502
2 106 0 369508879
150 200 0 576962057
99 9 0 588062163
101 72 0 148003923
9 182 0 732139947
84 88 0 720592694
198 161 0 151363245
89 187 0 214138025
160 150 0 82621350
63 170 0 665493133
135 144 0 571301198
118 29 ...

output:

0

result:

ok single line: '0'

Test #2:

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

input:

200 250
87 77 0 413690178
44 146 0 580238372
96 86 0 471635629
76 37 0 460314897
36 26 0 797795878
186 196 0 340458462
137 148 0 8238512
63 102 0 83585569
128 92 0 355539314
111 136 0 941271932
120 25 0 670904911
68 143 0 789757256
50 24 0 57273302
166 33 0 961114401
151 122 0 88660198
162 71 0 2027...

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 11ms
memory: 10172kb

input:

200 1000
32 195 208991 761039285
174 149 435536 435440777
109 29 693056 976975992
47 44 590890 186457226
80 65 353546 61953096
163 79 124971 309842392
5 82 341956 789963665
124 175 650665 600626885
46 79 450500 56179506
78 99 803108 312872894
194 48 926872 609270327
47 31 865000 911848359
113 46 598...

output:

2437514

result:

ok single line: '2437514'

Test #4:

score: 0
Accepted
time: 13ms
memory: 9724kb

input:

200 1000
200 164 902271 53884170
200 56 160646 471284489
118 17 548821 676285924
75 86 463453 741371140
124 183 677876 745454313
78 118 829257 377444281
26 137 315614 193865748
191 39 355032 923063487
29 171 281727 396954281
147 105 785551 455760667
161 19 730891 528269519
144 49 352247 321053381
15...

output:

2797127

result:

ok single line: '2797127'

Test #5:

score: 0
Accepted
time: 3ms
memory: 10924kb

input:

32 1000
16 15 124290 308896
6 18 503091 464441
5 26 710425 73322
30 9 502128 77143
15 19 378107 360904
20 10 857413 475127
23 19 732182 158395
30 11 646521 847592
10 21 400052 514680
16 20 254701 362685
29 2 302402 652641
1 31 171216 961419
9 24 15977 616364
10 32 635354 712012
6 20 16048 515031
7 1...

output:

298489

result:

ok single line: '298489'

Test #6:

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

input:

200 250
196 111 774995 586221052
17 177 831588 26974950
164 84 714701 648810834
17 13 742157 618387545
85 147 888921 259372421
154 15 298654 78188800
173 169 110484 573489855
127 64 365056 388013540
82 151 610677 517180859
159 123 947809 628375445
39 107 479215 223508800
111 182 697301 882646990
197...

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

2 1
1 2 295445 873561966

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 2ms
memory: 9940kb

input:

2 1
2 1 237201 424844240

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 3ms
memory: 9160kb

input:

2 1000
1 2 402668 186853963
1 2 735949 714240522
1 2 890366 761125200
1 2 951814 194495679
1 2 99029 557310684
1 2 617215 419379276
1 2 549225 178839633
1 2 355323 573589917
1 2 937541 928362249
1 2 868758 781946304
1 2 767929 303821251
1 2 626242 479948170
1 2 813810 44652483
1 2 171218 226464554
1...

output:

716875

result:

ok single line: '716875'

Test #10:

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

input:

200 1000
178 18 403199 745306
138 157 793234 968778
50 142 870390 93621
109 67 999704 979412
116 22 9321 687633
1 63 899030 755605
121 60 745634 834563
80 66 360811 865058
88 193 822514 784092
172 92 670903 360385
152 32 902998 468642
170 106 4454 31995
179 127 691910 841564
42 16 377120 79150
40 30...

output:

2031511

result:

ok single line: '2031511'

Test #11:

score: 0
Accepted
time: 15ms
memory: 9408kb

input:

200 1000
102 34 9765 492340
40 51 974965 910912
150 79 622386 108020
5 24 923983 390013
124 147 685146 380706
196 166 486 13100
11 192 391732 303741
103 182 3396 952309
104 196 8579 92828
14 108 456347 495057
71 158 524650 639348
48 171 489031 870958
106 123 757519 469153
49 119 314 286212
38 119 63...

output:

1952385

result:

ok single line: '1952385'

Test #12:

score: 0
Accepted
time: 11ms
memory: 9472kb

input:

200 1000
147 58 8369 679288
127 43 561908 768977
190 37 225224 36886
72 61 976059 334027
134 107 495719 115758
175 198 8231 409372
77 37 873272 382176
150 200 6384 475014
16 92 209657 234021
87 42 628084 846766
84 64 980603 242788
60 53 997 3242
145 22 603669 412271
128 155 680529 398679
181 78 7791...

output:

2118142

result:

ok single line: '2118142'

Test #13:

score: 0
Accepted
time: 9ms
memory: 9132kb

input:

200 1000
11 130 791191 404176588
11 122 563555 56058088
30 152 148445 539862143
198 103 120872 72731844
104 84 249798 911595238
43 170 461746 606803643
131 166 766080 370530123
162 133 422234 55245031
49 17 482082 886905498
23 57 368967 740007727
82 16 852072 87081727
138 117 178612 293980051
197 60...

output:

10868146

result:

ok single line: '10868146'

Test #14:

score: 0
Accepted
time: 11ms
memory: 8956kb

input:

200 1000
33 168 764973 324367398
12 123 829830 598733437
131 111 376329 424202715
54 69 590082 795737748
126 142 966806 201764048
5 123 239136 712318652
151 128 288844 25751551
57 26 498394 373677403
131 2 857656 108946841
106 149 377721 830446828
58 188 330376 582002477
34 119 188444 757594629
175 ...

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 7ms
memory: 9536kb

input:

200 1000
160 124 613071 696182916
159 74 870937 706697190
44 186 440707 437083079
2 21 819503 733229200
138 175 692401 889850109
200 73 624745 475215360
187 71 294075 625347482
166 187 340630 873369287
58 98 558584 834147686
96 121 537329 89196024
7 78 943459 205771934
47 38 675193 450415293
155 173...

output:

150860521

result:

ok single line: '150860521'

Test #16:

score: 0
Accepted
time: 11ms
memory: 9636kb

input:

200 1000
139 85 612404 678107446
193 167 370424 299825457
133 80 337021 807058141
166 76 848124 361695195
91 56 488427 208862978
18 181 906083 917428464
197 58 724726 876386772
132 170 819233 420219361
144 34 261383 50158753
64 132 565045 986404728
63 143 622103 188681921
46 57 468678 33496975
12 63...

output:

69441539

result:

ok single line: '69441539'

Subtask #2:

score: 11
Accepted

Test #17:

score: 11
Accepted
time: 74ms
memory: 11692kb

input:

200 50000
92 72 987034 981351
92 72 987034 428035
95 16 263441 869630
95 16 263441 274419
18 67 742896 495941
18 67 742896 773584
89 7 456457 702434
89 7 456457 631522
52 193 188333 207969
52 193 188333 151198
32 144 801401 523873
32 144 801401 485433
114 30 945638 685397
114 30 945638 387101
177 94...

output:

74778

result:

ok single line: '74778'

Test #18:

score: 0
Accepted
time: 69ms
memory: 12684kb

input:

200 50000
81 155 486782 27097
81 155 486782 30620
65 75 59187 75093
65 75 59187 51054
31 190 789785 30068
31 190 789785 16202
58 38 566251 4489
58 38 566251 61638
194 69 289219 52154
194 69 289219 80891
41 40 397430 4453
41 40 397430 4278
72 56 117479 27319
72 56 117479 38818
109 124 340726 86770
10...

output:

109918

result:

ok single line: '109918'

Test #19:

score: 0
Accepted
time: 70ms
memory: 13132kb

input:

200 50000
194 55 234429 708410426
194 55 234429 384608458
131 62 632898 21573777
131 62 632898 37126223
61 30 49016 414926917
61 30 49016 492949337
146 101 784073 746739995
146 101 784073 146060410
64 178 56224 667342312
64 178 56224 299393236
7 91 936860 109692693
7 91 936860 194842881
164 81 84869...

output:

57252

result:

ok single line: '57252'

Test #20:

score: 0
Accepted
time: 23ms
memory: 10168kb

input:

200 2000
116 131 203360 66508
116 131 203360 67230
26 141 575143 34427
26 141 575143 77629
154 82 502294 95098
154 82 502294 65235
1 193 302812 46125
1 193 302812 72261
50 184 595111 90817
50 184 595111 18649
148 30 152630 1823
148 30 152630 86395
47 59 166343 69998
47 59 166343 95536
190 165 245060...

output:

828749

result:

ok single line: '828749'

Test #21:

score: 0
Accepted
time: 21ms
memory: 10072kb

input:

200 1000
147 23 564780 98983
147 23 564780 71844
188 96 81113 23817
188 96 81113 56241
153 85 58212 86706
153 85 58212 98571
121 186 960850 68381
121 186 960850 72395
104 149 600259 10699
104 149 600259 55413
22 96 386801 32688
22 96 386801 97358
46 120 965304 95681
46 120 965304 58651
123 60 587695...

output:

3690675

result:

ok single line: '3690675'

Test #22:

score: 0
Accepted
time: 3ms
memory: 9040kb

input:

200 600
74 110 929330 83664
74 110 929330 20874
166 5 33508 96404
166 5 33508 41720
88 128 818761 42786
88 128 818761 40956
20 108 766115 85683
20 108 766115 28533
131 165 219493 60839
131 165 219493 99041
19 8 419476 19291
19 8 419476 87359
170 20 560605 98795
170 20 560605 20192
104 22 632991 8072...

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0
Accepted
time: 4ms
memory: 10000kb

input:

200 400
45 117 275789 93012
45 117 275789 52598
163 170 820126 32247
163 170 820126 41566
141 169 24624 60217
141 169 24624 6281
191 151 551490 41877
191 151 551490 65565
62 60 357388 48608
62 60 357388 68156
4 26 925710 14618
4 26 925710 53045
161 54 666405 11130
161 54 666405 68986
100 78 223759 4...

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0
Accepted
time: 2ms
memory: 10900kb

input:

2 2
1 2 92741 340404159
1 2 92741 831847090

output:

340589641

result:

ok single line: '340589641'

Test #25:

score: 0
Accepted
time: 22ms
memory: 12296kb

input:

200 50000
167 131 309677 812507597
167 131 309677 892266405
190 21 29794 932427342
190 21 29794 985563523
78 123 738421 166800465
78 123 738421 988088991
158 159 608112 93788118
158 159 608112 659413445
23 33 785815 821471444
23 33 785815 207475228
129 137 586187 539040339
129 137 586187 232837741
1...

output:

1058383

result:

ok single line: '1058383'

Test #26:

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

input:

200 50000
57 184 933538 477166241
57 184 933538 658767255
145 23 241505 451205305
145 23 241505 608320303
134 138 487648 967211125
134 138 487648 36072339
158 126 524877 653519294
158 126 524877 545581325
179 173 142381 67668130
179 173 142381 658272340
128 169 974357 11241080
128 169 974357 1401169...

output:

1030219

result:

ok single line: '1030219'

Test #27:

score: 0
Accepted
time: 48ms
memory: 12832kb

input:

200 50000
188 25 360135 645871074
188 25 360135 389126552
163 59 731381 227693202
163 59 731381 341331686
123 138 611363 158986141
123 138 611363 821324052
37 46 775282 404442458
37 46 775282 143939245
154 110 409608 719074279
154 110 409608 531184651
33 1 637926 885016182
33 1 637926 703632457
127 ...

output:

973754371

result:

ok single line: '973754371'

Test #28:

score: 0
Accepted
time: 56ms
memory: 12252kb

input:

200 50000
155 193 853618 557627289
155 193 853618 583166856
195 158 635013 77304682
195 158 635013 864313916
93 184 123347 731094785
93 184 123347 57648659
166 186 174915 160695869
166 186 174915 278505177
147 108 231084 564109148
147 108 231084 27452986
11 153 99276 124717233
11 153 99276 979571092...

output:

163491616

result:

ok single line: '163491616'

Test #29:

score: 0
Accepted
time: 52ms
memory: 12656kb

input:

200 50000
157 131 559779 704810941
157 131 559779 991998390
102 188 155246 188733734
102 188 155246 197619987
50 91 117732 432716633
50 91 117732 386411435
100 62 194970 295817161
100 62 194970 77364564
27 47 391518 469789775
27 47 391518 417317399
158 41 659908 673083808
158 41 659908 244885511
43 ...

output:

532304304

result:

ok single line: '532304304'

Test #30:

score: 0
Accepted
time: 51ms
memory: 12136kb

input:

200 50000
127 121 920108 139692795
127 121 920108 303802994
127 118 388346 383992026
127 118 388346 413397317
100 92 968538 679673421
100 92 968538 758160554
21 188 375244 201412702
21 188 375244 106779409
30 175 734692 910657430
30 175 734692 134718988
101 153 27145 60123711
101 153 27145 915838421...

output:

26170464

result:

ok single line: '26170464'

Subtask #3:

score: 21
Accepted

Test #31:

score: 21
Accepted
time: 5ms
memory: 10956kb

input:

200 1000
29 42 0 73206665
155 127 0 684640269
50 198 0 321195054
144 61 0 823740117
102 146 0 503128895
56 38 0 739648322
181 24 0 720383720
197 37 0 235418116
57 184 0 493283302
125 96 0 845930225
11 59 0 18751364
101 122 0 175819721
123 151 0 99670888
111 194 0 526645991
132 64 0 904239661
103 173...

output:

0

result:

ok single line: '0'

Test #32:

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

input:

200 250
72 162 0 953534115
152 94 0 541492633
58 118 0 389246378
118 137 0 266112508
21 100 0 546059320
26 28 0 396924657
155 69 0 955241958
123 102 0 483117471
160 39 0 787307136
31 80 0 230131728
33 69 0 459221426
149 126 0 356240138
128 99 0 991905541
7 57 0 28752914
149 6 0 761950451
23 150 0 66...

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0
Accepted
time: 42ms
memory: 12072kb

input:

200 39000
5 128 0 263267641
153 85 0 899842112
187 180 0 595861423
104 180 0 342805606
46 128 0 402084500
149 35 0 569501214
103 161 0 260423816
141 134 0 45988579
46 84 0 733407435
102 72 0 411807981
16 93 0 653975947
136 122 0 802943341
194 12 0 486663003
15 39 0 756041482
114 102 0 81270200
29 17...

output:

0

result:

ok single line: '0'

Test #34:

score: 0
Accepted
time: 4ms
memory: 9144kb

input:

200 250
25 149 0 828344450
147 92 0 105355875
161 134 0 394468995
126 133 0 983016958
166 198 0 636967133
194 27 0 476102140
161 125 0 563707449
12 107 0 940601555
166 43 0 341231414
29 127 0 330417177
42 151 0 515152204
174 148 0 779725082
196 98 0 433119501
98 141 0 58726839
191 119 0 70093707
138...

output:

-1

result:

ok single line: '-1'

Test #35:

score: 0
Accepted
time: 64ms
memory: 13428kb

input:

200 50000
47 114 0 28662264
167 94 0 869928657
164 114 0 867884340
169 160 0 875464672
12 26 0 631902204
107 34 0 896158526
43 166 0 171450054
153 141 0 918639184
176 126 0 213629871
52 93 0 57972464
113 98 0 135524408
180 45 0 204882610
16 119 0 836482116
166 15 0 18941237
34 164 0 91653141
178 41 ...

output:

0

result:

ok single line: '0'

Test #36:

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

input:

2 1
1 2 0 437141402

output:

-1

result:

ok single line: '-1'

Test #37:

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

input:

2 1
2 1 0 509980359

output:

-1

result:

ok single line: '-1'

Test #38:

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

input:

200 50000
101 173 0 96328184
53 37 0 682216281
66 46 0 984697439
11 179 0 962449275
8 150 0 830303960
7 149 0 968194366
5 140 0 765556136
60 181 0 227023278
170 198 0 285977076
49 86 0 711569364
17 36 0 849371329
46 81 0 191985437
39 174 0 831451095
54 37 0 927367745
191 140 0 600718495
50 28 0 3459...

output:

48745

result:

ok single line: '48745'

Test #39:

score: 0
Accepted
time: 31ms
memory: 13732kb

input:

200 50000
121 77 0 944537760
152 142 0 266262195
152 34 0 166865975
53 191 0 948032019
76 97 0 619799895
18 98 0 472635632
46 19 0 803089882
177 125 0 582285375
74 154 0 552381005
9 103 0 71099043
30 63 0 336022032
63 44 0 174296374
68 168 0 471158327
122 27 0 883408538
99 97 0 858933944
16 157 0 58...

output:

15811

result:

ok single line: '15811'

Test #40:

score: 0
Accepted
time: 75ms
memory: 12716kb

input:

200 50000
4 94 0 216959703
200 149 0 312529063
4 135 0 626082026
80 47 0 979415352
12 60 0 641039482
27 123 0 972824693
200 43 0 153733401
51 184 0 137934127
197 123 0 187738894
115 12 0 624851409
142 154 0 494153133
185 179 0 291605828
161 116 0 617701833
88 119 0 269797341
86 83 0 537023729
89 19 ...

output:

-1

result:

ok single line: '-1'

Test #41:

score: 0
Accepted
time: 70ms
memory: 13648kb

input:

200 50000
69 135 0 229204322
176 34 0 799753369
142 146 0 602811107
189 58 0 591020196
126 52 0 32316809
152 122 0 143395253
196 97 0 424467048
80 195 0 90045088
145 142 0 739369269
113 156 0 666451383
103 192 0 612994988
77 132 0 865072127
72 151 0 138527285
51 75 0 493119803
133 192 0 462503170
13...

output:

-1

result:

ok single line: '-1'

Test #42:

score: 0
Accepted
time: 82ms
memory: 14268kb

input:

200 50000
178 67 0 820891840
137 158 0 1088392
116 131 0 414032428
195 127 0 679019898
135 158 0 342893460
133 15 0 284005235
53 151 0 694243013
191 199 0 544614532
105 156 0 959928506
126 174 0 127181954
76 2 0 226974605
192 60 0 473260028
31 29 0 542385990
9 23 0 825658824
111 140 0 700415184
92 5...

output:

-1

result:

ok single line: '-1'

Test #43:

score: 0
Accepted
time: 3ms
memory: 10916kb

input:

2 2
1 2 0 453384442
1 2 0 775413690

output:

453384442

result:

ok single line: '453384442'

Test #44:

score: 0
Accepted
time: 3ms
memory: 10908kb

input:

2 2
1 2 0 337730766
1 2 0 365263699

output:

337730766

result:

ok single line: '337730766'

Test #45:

score: 0
Accepted
time: 3ms
memory: 9712kb

input:

2 2
1 2 0 31787600
1 2 0 244806432

output:

31787600

result:

ok single line: '31787600'

Test #46:

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

input:

2 2
2 1 0 818768622
2 1 0 811758986

output:

811758986

result:

ok single line: '811758986'

Test #47:

score: 0
Accepted
time: 2ms
memory: 9820kb

input:

2 2
1 2 0 517402843
1 2 0 322441846

output:

322441846

result:

ok single line: '322441846'

Test #48:

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

input:

2 2
1 2 0 564696995
1 2 0 461826765

output:

461826765

result:

ok single line: '461826765'

Test #49:

score: 0
Accepted
time: 51ms
memory: 13192kb

input:

200 50000
11 37 0 101921176
92 179 0 616115851
135 31 0 323591478
131 87 0 215758868
145 138 0 685461373
129 109 0 192556462
23 68 0 881628320
2 3 0 733338089
141 81 0 24245221
136 138 0 124078391
120 98 0 273400577
65 170 0 486566361
102 145 0 371995533
9 113 0 295670350
159 24 0 435405821
71 190 0...

output:

223003122

result:

ok single line: '223003122'

Test #50:

score: 0
Accepted
time: 42ms
memory: 13416kb

input:

200 50000
27 75 0 581461785
20 122 0 15409911
44 194 0 543381821
192 72 0 795502392
130 70 0 503459764
16 70 0 499744824
51 74 0 237357657
3 163 0 798003508
168 51 0 420541781
116 78 0 393621072
110 95 0 941962583
122 110 0 171735962
51 97 0 9019567
199 47 0 183244104
17 27 0 345617388
177 111 0 245...

output:

586267611

result:

ok single line: '586267611'

Test #51:

score: 0
Accepted
time: 58ms
memory: 12908kb

input:

200 50000
28 94 0 80147689
174 44 0 25829559
12 109 0 631274491
61 198 0 241532299
118 80 0 810189242
182 74 0 131307466
140 43 0 370536030
89 92 0 534082772
12 95 0 514780745
47 189 0 24159531
192 90 0 158943936
79 92 0 565584175
198 188 0 238784342
13 78 0 626221887
14 173 0 673852561
89 190 0 326...

output:

342836942

result:

ok single line: '342836942'

Test #52:

score: 0
Accepted
time: 52ms
memory: 13360kb

input:

200 50000
16 20 0 305346379
191 2 0 605477889
48 94 0 600390557
160 37 0 581473100
128 103 0 659591944
162 173 0 892649418
51 95 0 59745842
46 199 0 800250719
72 23 0 440234036
80 97 0 254855388
149 14 0 181507238
19 12 0 832294157
165 191 0 948344489
32 150 0 856947512
26 116 0 827286570
87 198 0 6...

output:

301443506

result:

ok single line: '301443506'

Subtask #4:

score: 63
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #53:

score: 63
Accepted
time: 42ms
memory: 11928kb

input:

200 50000
109 199 866658 402822
198 146 821511 858622
48 126 775084 304677
30 170 773310 230542
127 88 361657 306645
89 38 586840 15436
196 99 680062 253860
197 101 590916 132086
63 196 813362 529610
83 79 631724 872955
93 17 694025 241917
120 4 649698 692442
29 138 29884 935359
40 70 144127 29045
1...

output:

39483

result:

ok single line: '39483'

Test #54:

score: 0
Accepted
time: 39ms
memory: 13324kb

input:

200 50000
86 53 937691 79957
115 72 221997 79633
196 156 895663 7611
23 128 490961 99949
13 149 35407 6091
156 142 171089 7794
22 58 307493 23356
55 25 837898 2463
112 61 770641 5991
13 153 968699 74731
186 118 796660 15588
87 173 808325 69659
74 40 736423 24016
112 12 632364 76942
36 89 268396 9307...

output:

46429

result:

ok single line: '46429'

Test #55:

score: 0
Accepted
time: 40ms
memory: 12060kb

input:

200 50000
105 182 451078 42931
76 11 641175 34837
64 7 561875 19340
27 19 470232 6514
117 24 969800 44864
136 117 472000 91034
91 115 107894 69761
174 144 130128 65721
111 112 976902 4732
111 49 770627 46709
23 115 636642 30233
53 28 12843 35747
67 18 846480 53298
167 101 19608 44917
30 153 707535 2...

output:

32458

result:

ok single line: '32458'

Test #56:

score: 0
Accepted
time: 11ms
memory: 10812kb

input:

200 1000
24 26 998375 471068176
27 10 798973 542493630
139 41 817708 917903406
164 3 575556 858366820
5 80 618453 808977780
100 4 702884 822565798
134 105 167381 604240630
184 176 639886 412404600
9 120 782429 331622140
169 109 607585 607621454
41 75 773135 731250664
95 168 648386 10908955
43 179 68...

output:

2990263

result:

ok single line: '2990263'

Test #57:

score: 0
Accepted
time: 11ms
memory: 10720kb

input:

200 1000
155 10 894748 123114562
106 193 621709 180477121
53 45 526398 769834495
10 31 742284 312892238
11 37 445937 110546652
37 30 947385 303659469
189 75 766838 273123229
88 15 782209 808865530
130 82 427693 429877888
48 120 586188 185380140
179 65 162415 205285255
68 129 193452 53171686
193 55 4...

output:

1582172

result:

ok single line: '1582172'

Test #58:

score: 0
Accepted
time: 29ms
memory: 11484kb

input:

200 40000
125 167 615226 903948
7 79 934825 102826
8 24 719545 377058
156 4 916302 906459
79 14 787821 37684
128 195 300402 965365
42 119 754405 293604
172 71 859075 975979
14 37 847968 46288
156 143 754335 375832
15 193 334440 373820
51 82 826638 765652
151 147 986378 710160
61 98 313397 296665
64 ...

output:

1664208

result:

ok single line: '1664208'

Test #59:

score: 0
Accepted
time: 37ms
memory: 12696kb

input:

200 40000
119 105 305900 93106
151 16 725015 717224
97 45 237381 692966
18 93 875793 557857
119 59 949379 101822
91 129 444896 111555
144 177 922343 681257
78 181 799690 477869
30 158 335464 958975
82 24 608518 380400
76 127 762632 687956
182 114 544562 349
14 114 583759 769619
147 136 753053 446257...

output:

1787594

result:

ok single line: '1787594'

Test #60:

score: 0
Accepted
time: 29ms
memory: 11192kb

input:

200 40000
184 30 811102 74681
50 95 962820 294144
5 105 366021 511571
7 47 455978 976284
127 14 347768 749762
133 118 498925 715035
32 97 604485 368107
139 15 847592 897968
36 56 889089 498367
42 137 620334 737884
178 8 690655 756638
112 67 477442 87663
42 63 474085 848458
153 53 676538 410740
11 9 ...

output:

2015338

result:

ok single line: '2015338'

Test #61:

score: 0
Accepted
time: 37ms
memory: 11408kb

input:

200 40000
98 135 948198 702738
121 67 783654 636049
117 18 967396 583610
140 98 413069 104029
123 46 753268 989309
131 175 957181 364956
40 49 805724 810430
82 39 532159 220145
95 165 905210 402262
153 163 891455 695556
135 175 699714 343488
82 7 865809 357585
51 141 767270 738655
10 37 359587 12056...

output:

2102256

result:

ok single line: '2102256'

Test #62:

score: 0
Accepted
time: 33ms
memory: 11552kb

input:

200 40000
16 93 562723 611155
193 18 962532 831346
45 91 851401 459624
27 87 919368 768965
173 101 253016 745945
139 11 843742 793371
125 185 613096 712336
175 63 740805 868641
75 173 863332 675430
43 171 697089 294632
60 68 574818 764093
89 72 994617 879126
143 72 580737 741918
164 108 9079 406130
...

output:

2045978

result:

ok single line: '2045978'

Test #63:

score: 0
Accepted
time: 34ms
memory: 12600kb

input:

200 40000
2 156 790895 902294
27 139 868338 381336
52 13 489396 634228
190 152 836583 419655
33 158 708671 892720
122 149 980224 374866
12 82 344641 322090
141 100 334693 247895
55 116 859877 245727
199 98 512711 914909
124 95 964391 798250
54 116 525412 777111
191 179 705067 419709
167 11 941439 24...

output:

1958694

result:

ok single line: '1958694'

Test #64:

score: 0
Accepted
time: 37ms
memory: 11220kb

input:

200 40000
175 148 301913 941053
143 4 673892 992819
122 101 114149 574637
192 118 954145 783901
183 143 937183 726579
141 107 74444 188138
11 178 374111 869952
96 88 50183 326712
192 91 595523 229844
111 93 767406 59279
110 150 502724 47940
41 102 841798 212580
68 30 943201 300687
199 85 378303 3247...

output:

2094093

result:

ok single line: '2094093'

Test #65:

score: 0
Accepted
time: 29ms
memory: 12088kb

input:

200 40000
114 19 254715 768926
132 81 946544 484258
51 67 144518 589985
133 95 272859 394035
99 37 926997 927414
179 48 465408 257565
1 121 802445 963060
154 36 244273 640602
170 17 185364 696247
31 151 845049 321502
63 82 621263 837538
77 87 869993 173833
130 195 95277 360474
35 88 803679 206930
63...

output:

1969522

result:

ok single line: '1969522'

Test #66:

score: 0
Accepted
time: 33ms
memory: 12600kb

input:

200 40000
28 16 208204 383848
29 170 790051 263755
187 167 350269 677082
83 191 91654 143498
140 148 431596 502454
175 53 777451 463908
58 95 240314 841023
75 196 916423 759350
183 169 582529 744286
190 195 646843 984134
116 200 324178 953601
137 119 625226 283817
15 131 569236 854965
65 133 162133 ...

output:

2040068

result:

ok single line: '2040068'

Test #67:

score: 0
Accepted
time: 9ms
memory: 12044kb

input:

2 40000
2 1 797448 933460473
2 1 161238 660389792
2 1 416054 914125163
2 1 367675 203672509
2 1 725208 315707172
2 1 615913 108423144
2 1 277485 552980036
2 1 304017 929855813
2 1 404932 219633805
2 1 982129 55070408
2 1 335013 275609397
2 1 3499 239103084
2 1 756024 392361332
2 1 400001 953432057
2...

output:

75564

result:

ok single line: '75564'

Test #68:

score: 0
Accepted
time: 21ms
memory: 13104kb

input:

200 50000
107 102 659030 977274169
72 14 474428 995944990
40 53 729891 149177173
120 52 976078 268870195
68 27 373466 716822736
127 124 171081 213349473
101 109 701847 860629710
108 87 960707 267493586
2 152 792118 356248347
110 166 807038 280185661
148 170 611379 453058415
91 180 130893 885870495
1...

output:

354454

result:

ok single line: '354454'

Test #69:

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

input:

200 50000
20 94 894455 27525973
44 184 493725 624612904
163 7 73902 591173065
17 73 308018 126380765
112 77 858246 330932512
177 169 581835 814917460
40 124 78739 136623170
90 122 756493 53618046
111 191 546501 819585875
138 166 750110 503328788
170 49 967034 433619364
113 168 186466 14203158
123 17...

output:

425591

result:

ok single line: '425591'

Test #70:

score: 0
Accepted
time: 36ms
memory: 12992kb

input:

200 50000
109 128 317252 464492482
73 51 737491 204349124
125 126 398430 295463013
1 91 412693 349660486
95 20 690693 511325653
50 58 416338 635050820
161 32 241370 783107288
127 94 491761 321419129
96 190 521005 106365220
131 63 337226 952119908
115 177 728691 530459803
190 85 390524 422426854
3 12...

output:

-1

result:

ok single line: '-1'

Test #71:

score: 0
Accepted
time: 30ms
memory: 12792kb

input:

200 50000
133 155 674197 830025447
141 26 27640 495584699
22 38 438507 104671703
126 188 108260 738103050
115 25 13331 380820203
77 121 499278 806241595
25 52 328877 353256179
94 162 270399 135040901
10 43 556226 633372799
194 46 491536 678474879
57 198 422668 380942618
63 133 157920 165889078
97 16...

output:

12402874

result:

ok single line: '12402874'

Test #72:

score: 0
Accepted
time: 31ms
memory: 11904kb

input:

200 50000
24 53 305573 622901331
46 134 113303 589294049
198 132 977216 219315562
200 97 913064 209563230
52 195 976019 486987836
175 158 782747 716671755
186 178 686667 844462881
39 125 595980 386854021
180 99 264847 375997081
142 59 542444 443851159
98 178 138496 186733627
36 155 163408 647857493
...

output:

589162183

result:

ok single line: '589162183'

Test #73:

score: 0
Accepted
time: 31ms
memory: 12156kb

input:

200 50000
27 32 972383 852007900
74 157 177669 331166283
38 24 96364 522554699
197 168 342012 731348331
96 95 612152 604571680
99 180 13307 31814282
52 173 929791 464489262
199 23 145367 319889689
42 142 236184 142620736
22 158 391368 964076597
175 27 972306 129001910
14 59 191889 621723901
197 2 39...

output:

98397375

result:

ok single line: '98397375'

Test #74:

score: 0
Accepted
time: 35ms
memory: 12400kb

input:

200 50000
41 167 117543 245942774
5 147 794078 717895557
147 190 749017 743236293
175 110 694879 477583631
33 18 569917 174477856
116 7 606174 131967552
36 110 351071 378141487
31 76 209372 540082298
107 31 788337 668808088
116 129 681871 901042786
158 150 238259 736446353
51 116 919420 493091129
10...

output:

127834001

result:

ok single line: '127834001'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2025-02-01 20:53:32 | 开源项目