QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547882 | #3144. Soccer | kkkgjyismine4 | 100 ✓ | 361ms | 128388kb | C++20 | 1.8kb | 2024-09-05 12:05:03 | 2024-09-05 12:05:04 |
Judging History
answer
#include<bits/stdc++.h>
#define N 100005
#define M 505
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const ll inf=1e18;
int n,m,ct,X[N],Y[N],A,B,C;
ll dis[N<<5];
int tot,id[3][M][M],mk[N<<5],fl[M][M],mn[M][M];
vector<pii>road[N<<5];
void add(int u,int v,ll c){road[u].pb(mp(v,c));}
void Add(int u,int v,ll c){add(u,v,c),add(v,u,c);}
priority_queue<pii>pq;
void dj(int S){
for(int i=1;i<=tot;++i)dis[i]=inf;
dis[S]=0,pq.push(mp(-dis[S],S));
while(pq.size()){
int x=pq.top().se;pq.pop();
if(mk[x])continue;mk[x]=1;
for(auto v:road[x])
if(dis[v.fi]>dis[x]+v.se)
dis[v.fi]=dis[x]+v.se,pq.push(mp(-dis[v.fi],v.fi));
}
}
queue<pii>q;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void Init(){
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j){
mn[i][j]=(fl[i][j]?0:1e9);
if(!mn[i][j])q.push(mp(i,j));
}
while(q.size()){
pii a=q.front();q.pop();
int x=a.fi,y=a.se;
for(int i=0,px,py;i<4;++i){
px=x+dx[i],py=y+dy[i];
if(mn[px][py]>mn[x][y]+1)mn[px][py]=mn[x][y]+1,q.push(mp(px,py));
}
}
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&C,&ct);
for(int i=1;i<=ct;++i)scanf("%d%d",&X[i],&Y[i]),fl[X[i]][Y[i]]=1;
Init();
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j){
id[0][i][j]=++tot;
id[1][i][j]=++tot,id[2][i][j]=++tot;
add(id[0][i][j],id[1][i][j],B);
add(id[0][i][j],id[2][i][j],B);
add(id[1][i][j],id[0][i][j],1ll*C*mn[i][j]);
add(id[2][i][j],id[0][i][j],1ll*C*mn[i][j]);
}
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j){
if(i<n)Add(id[1][i][j],id[1][i+1][j],A),Add(id[0][i][j],id[0][i+1][j],C);
if(j<m)Add(id[2][i][j],id[2][i][j+1],A),Add(id[0][i][j],id[0][i][j+1],C);
}
dj(id[0][X[1]][Y[1]]);
cout<<dis[id[0][X[ct]][Y[ct]]];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 72ms
memory: 37868kb
input:
300 200 100 6079 1886 2 241 4 156 199
output:
185889
result:
ok single line: '185889'
Test #2:
score: 5
Accepted
time: 4ms
memory: 9936kb
input:
1 100 2000 25006 20 2 0 0 1 100
output:
2020
result:
ok single line: '2020'
Test #3:
score: 5
Accepted
time: 303ms
memory: 124472kb
input:
500 500 800 1678 1000000000 2 386 366 274 261
output:
105000091278
result:
ok single line: '105000091278'
Test #4:
score: 5
Accepted
time: 322ms
memory: 125552kb
input:
500 500 100 1000 100000000 2 257 486 199 215
output:
5800028100
result:
ok single line: '5800028100'
Test #5:
score: 5
Accepted
time: 59ms
memory: 50308kb
input:
350 261 1000000000 1000000000 1000000000 2 295 110 100 167
output:
252000000000
result:
ok single line: '252000000000'
Subtask #2:
score: 30
Accepted
Test #6:
score: 30
Accepted
time: 290ms
memory: 122400kb
input:
500 500 0 300696907 209698877 50 332 412 270 95 483 481 140 413 12 437 280 271 229 120 182 239 29 322 129 84 239 344 325 39 268 446 14 495 404 269 289 390 87 199 318 157 366 389 129 186 95 183 39 341 88 458 74 19 349 10 416 119 465 7 246 30 330 100 376 283 479 104 202 236 118 43 411 189 37 236 252 3...
output:
3537178092
result:
ok single line: '3537178092'
Test #7:
score: 30
Accepted
time: 307ms
memory: 122652kb
input:
500 500 0 93603960 309687788 80 296 178 107 252 119 76 160 188 215 496 222 71 372 202 118 377 42 364 437 148 443 468 67 464 259 384 56 195 189 154 334 300 198 367 435 261 321 433 12 325 210 143 120 483 20 416 327 8 418 23 436 414 370 278 64 287 384 434 90 92 32 292 227 129 396 485 378 268 403 212 27...
output:
2542230356
result:
ok single line: '2542230356'
Test #8:
score: 30
Accepted
time: 240ms
memory: 101596kb
input:
400 500 0 196986778 205776678 100 62 85 340 444 104 154 314 421 139 205 292 287 17 5 57 12 124 130 22 37 228 270 200 366 17 119 232 363 121 137 203 332 141 245 304 422 187 157 295 284 99 34 224 293 146 145 321 439 84 2 363 497 84 79 239 296 259 332 54 68 303 497 123 156 398 400 3 23 386 477 293 323 ...
output:
9180841410
result:
ok single line: '9180841410'
Test #9:
score: 30
Accepted
time: 219ms
memory: 123900kb
input:
500 500 0 2909687 909887887 100 0 0 130 132 219 217 208 208 56 58 194 194 461 460 461 460 55 56 72 73 127 129 244 245 469 471 11 12 375 375 417 415 110 109 97 99 310 310 2 2 395 397 330 331 401 399 62 60 209 208 494 495 410 409 41 42 359 359 196 194 77 77 285 285 348 349 428 427 177 179 297 298 234 ...
output:
405964211013
result:
ok single line: '405964211013'
Test #10:
score: 30
Accepted
time: 238ms
memory: 102496kb
input:
500 400 0 999999999 1000000000 200 446 318 186 27 182 47 235 106 184 158 340 204 269 391 466 281 237 53 444 276 429 385 300 400 286 274 481 235 21 75 472 246 231 141 185 68 143 41 463 321 296 222 499 306 95 149 72 190 305 382 115 77 363 366 356 207 300 216 396 325 8 167 225 10 148 127 388 376 231 18...
output:
23999999992
result:
ok single line: '23999999992'
Test #11:
score: 30
Accepted
time: 234ms
memory: 127892kb
input:
500 500 0 5188667 95867777 1000 0 0 80 79 281 280 499 500 357 355 244 244 346 347 240 239 248 246 482 482 320 321 162 162 353 355 226 226 56 56 175 175 114 114 343 344 429 429 210 209 171 171 169 170 52 52 400 400 461 460 233 231 173 173 200 198 115 117 151 151 63 62 437 438 123 125 363 362 82 83 19...
output:
12762997800
result:
ok single line: '12762997800'
Test #12:
score: 30
Accepted
time: 284ms
memory: 125540kb
input:
500 500 0 9598867 399868778 1000 499 370 406 8 146 375 109 441 40 414 389 53 173 178 480 77 350 219 35 342 481 104 8 395 358 182 363 200 273 17 373 499 393 460 283 15 10 305 140 425 166 14 240 298 130 384 357 177 408 500 326 272 287 235 324 207 254 142 261 145 106 252 1 284 361 178 75 48 236 139 251...
output:
86389803
result:
ok single line: '86389803'
Test #13:
score: 30
Accepted
time: 274ms
memory: 126236kb
input:
500 500 0 38301012 423639549 1000 118 85 485 444 174 154 393 421 142 205 257 287 40 5 111 12 191 130 1 37 336 270 305 366 61 119 337 363 165 137 257 332 142 245 443 422 235 157 295 284 44 34 266 293 131 145 467 439 112 2 436 497 30 79 331 296 275 332 31 68 398 497 169 156 438 400 107 23 421 477 272 ...
output:
842622264
result:
ok single line: '842622264'
Test #14:
score: 30
Accepted
time: 303ms
memory: 125276kb
input:
500 500 0 834442619 598809884 1000 156 222 234 491 496 220 450 238 5 311 157 259 258 333 337 257 204 19 170 370 116 388 132 214 82 184 430 327 255 320 223 262 478 183 47 5 449 461 115 264 322 434 90 398 100 240 136 267 190 137 88 218 12 2 57 135 129 74 364 369 205 212 399 263 430 158 370 433 272 374...
output:
2866505006
result:
ok single line: '2866505006'
Test #15:
score: 30
Accepted
time: 28ms
memory: 29112kb
input:
500 80 0 556697145 194068309 1000 71 76 316 48 430 46 252 55 263 21 250 64 54 55 472 62 353 20 237 39 218 37 437 73 9 17 377 47 170 15 109 6 467 8 388 34 393 3 482 38 80 64 228 27 220 1 190 67 110 7 119 36 264 45 477 28 370 79 418 23 388 44 363 48 476 57 250 55 269 16 367 5 4 59 132 52 401 66 248 42...
output:
1695599217
result:
ok single line: '1695599217'
Test #16:
score: 30
Accepted
time: 286ms
memory: 122236kb
input:
500 500 0 1 1000000000 1000 254 199 441 166 206 75 221 375 112 328 65 246 248 328 118 467 186 324 342 103 307 463 188 465 93 113 244 51 395 434 373 104 112 254 321 405 191 61 419 138 157 103 346 303 489 81 101 109 366 152 266 65 310 115 219 259 409 33 361 448 155 429 129 346 276 485 28 114 461 298 4...
output:
3000000008
result:
ok single line: '3000000008'
Test #17:
score: 30
Accepted
time: 292ms
memory: 124460kb
input:
500 500 0 241151 1000000000 150 119 51 100 500 359 405 233 155 141 400 258 453 98 445 493 181 94 308 46 460 355 419 207 131 111 349 248 150 340 364 100 39 18 399 326 220 238 184 452 84 482 144 364 295 68 187 461 110 390 115 428 252 63 79 273 318 351 465 58 78 90 152 288 161 164 389 412 62 465 2 74 4...
output:
12001446906
result:
ok single line: '12001446906'
Test #18:
score: 30
Accepted
time: 187ms
memory: 102840kb
input:
400 500 0 17777 1000000000 1000 0 0 219 277 331 416 242 303 226 282 279 351 268 334 210 263 242 303 302 381 300 376 382 480 367 459 298 374 27 33 281 352 15 15 345 432 66 81 262 328 186 235 264 330 332 417 192 237 98 121 139 173 116 143 156 192 52 64 232 290 151 189 79 97 117 147 186 231 191 236 255...
output:
90005101999
result:
ok single line: '90005101999'
Test #19:
score: 30
Accepted
time: 289ms
memory: 124724kb
input:
500 500 0 9028 1000000000 1000 156 364 371 394 162 66 475 494 42 212 473 34 337 298 207 289 259 92 373 38 435 263 414 33 481 109 208 63 338 468 395 400 359 384 238 382 53 147 492 58 333 482 283 484 406 327 290 499 152 147 303 102 152 147 377 417 452 407 67 345 384 263 423 498 357 94 219 53 234 207 1...
output:
2000054168
result:
ok single line: '2000054168'
Test #20:
score: 30
Accepted
time: 212ms
memory: 101500kb
input:
500 400 0 3333333 1000000000 1000 234 28 381 87 188 341 306 62 379 213 461 398 329 319 175 225 236 344 183 54 377 381 275 209 102 59 231 318 1 277 53 93 95 171 98 277 279 11 459 252 469 339 149 250 419 218 290 327 206 13 412 139 107 320 297 92 408 323 417 354 281 302 166 243 453 237 0 43 207 256 114...
output:
2006666666
result:
ok single line: '2006666666'
Subtask #3:
score: 65
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 65
Accepted
time: 70ms
memory: 53820kb
input:
300 300 842479671 712647299 65454911 50 267 253 274 153 182 43 250 239 50 122 110 141 230 157 162 166 183 13 180 219 246 82 1 93 246 16 218 195 139 1 210 25 156 184 149 275 250 66 120 105 39 241 85 18 161 82 159 94 227 140 19 175 12 164 4 293 4 269 0 251 278 230 68 288 184 100 166 67 239 234 150 235...
output:
10930970137
result:
ok single line: '10930970137'
Test #22:
score: 65
Accepted
time: 346ms
memory: 126376kb
input:
500 500 57055586 951562629 666954229 100 312 397 366 441 49 1 190 58 72 21 478 255 353 443 342 363 212 133 168 119 155 206 4 72 401 480 91 68 318 336 304 316 461 463 212 207 322 305 279 290 255 292 253 368 457 396 138 205 157 22 284 339 216 102 5 159 332 256 454 313 195 186 374 382 133 88 50 166 99 ...
output:
51671798980
result:
ok single line: '51671798980'
Test #23:
score: 65
Accepted
time: 302ms
memory: 109808kb
input:
450 500 62341541 290961612 868129885 250 63 330 66 449 61 479 252 127 3 435 290 493 13 452 376 195 325 35 336 92 401 367 243 227 300 20 46 180 94 330 395 189 271 79 440 388 282 320 237 91 371 126 178 373 437 326 422 408 401 192 161 35 140 327 274 449 64 478 157 278 32 351 357 249 187 426 216 421 48 ...
output:
40327916248
result:
ok single line: '40327916248'
Test #24:
score: 65
Accepted
time: 345ms
memory: 124976kb
input:
500 500 19223723 588625738 461016708 1500 367 423 179 254 185 131 376 352 312 45 234 182 428 196 329 476 330 364 413 260 294 240 416 376 256 464 169 141 21 320 267 462 443 94 65 446 125 304 252 277 109 404 356 32 390 271 43 316 228 59 320 166 309 304 352 35 133 21 74 131 338 80 342 312 465 236 80 40...
output:
10568931772
result:
ok single line: '10568931772'
Test #25:
score: 65
Accepted
time: 335ms
memory: 125176kb
input:
500 500 122933428 28746315 965419391 3000 0 0 102 103 352 353 413 414 187 189 196 197 493 493 180 181 304 305 415 416 346 347 419 419 76 75 136 135 473 475 243 244 3 2 216 216 273 274 2 3 148 146 418 419 482 482 293 293 16 14 90 90 124 122 382 380 341 341 302 300 134 135 412 414 247 246 308 308 438 ...
output:
133434675803
result:
ok single line: '133434675803'
Test #26:
score: 65
Accepted
time: 336ms
memory: 123300kb
input:
500 500 69293816 712868499 530608039 8000 82 47 188 162 432 442 413 423 5 28 245 132 476 461 349 356 366 365 236 149 121 26 46 97 36 50 216 191 85 66 322 331 290 254 495 457 154 226 464 474 187 224 236 201 50 115 94 56 276 316 10 67 241 157 96 37 110 16 161 244 363 310 90 75 6 35 283 323 131 131 233...
output:
57811897624
result:
ok single line: '57811897624'
Test #27:
score: 65
Accepted
time: 203ms
memory: 119240kb
input:
500 500 650008046 6011562 529006259 70000 368 122 298 6 430 396 197 399 9 139 69 411 414 13 197 9 16 323 474 412 372 18 160 215 50 335 269 166 314 364 231 5 9 216 447 74 431 442 347 351 59 52 109 153 213 341 310 82 282 397 42 93 141 123 115 70 479 420 118 58 301 248 396 364 317 321 317 284 349 421 1...
output:
175101071729
result:
ok single line: '175101071729'
Test #28:
score: 65
Accepted
time: 239ms
memory: 119040kb
input:
500 500 452549052 380268484 837855372 100000 320 432 94 476 337 286 11 9 20 40 383 189 186 298 449 304 471 492 60 100 313 208 143 206 387 128 45 131 396 291 268 470 363 338 88 449 64 164 422 86 282 457 306 77 76 398 470 242 12 137 118 81 254 431 115 167 80 337 366 67 56 459 334 85 442 309 105 49 476...
output:
281793498260
result:
ok single line: '281793498260'
Test #29:
score: 65
Accepted
time: 318ms
memory: 120164kb
input:
500 500 208845324 176765527 516716687 100000 93 114 100 93 495 496 293 289 33 81 6 5 100 66 20 109 346 371 497 480 400 445 222 169 34 108 131 172 244 171 306 327 392 398 100 122 24 82 291 372 161 226 471 442 495 419 20 94 278 302 206 240 344 281 407 458 381 411 398 446 35 50 412 492 145 226 122 112 ...
output:
142898647955
result:
ok single line: '142898647955'
Test #30:
score: 65
Accepted
time: 234ms
memory: 121968kb
input:
500 500 999999998 0 999999999 100000 263 483 444 458 86 166 119 135 174 89 460 335 214 66 228 189 268 480 74 212 90 21 280 456 55 143 51 248 304 424 93 113 252 323 217 107 110 95 261 385 21 234 303 356 452 252 44 50 89 77 191 70 473 312 332 319 268 260 260 373 386 266 9 116 431 365 134 79 450 479 12...
output:
376999999246
result:
ok single line: '376999999246'
Test #31:
score: 65
Accepted
time: 336ms
memory: 123288kb
input:
500 500 1 10000 1000000000 1200 54 440 437 35 213 40 177 198 183 113 44 381 228 100 300 275 107 486 152 60 72 196 307 266 207 93 246 393 176 176 28 156 74 405 61 298 68 414 48 120 193 378 399 427 100 303 397 73 142 391 449 315 396 322 311 71 23 241 274 318 393 431 363 355 231 206 382 292 471 8 25 13...
output:
2000040809
result:
ok single line: '2000040809'
Test #32:
score: 65
Accepted
time: 357ms
memory: 126648kb
input:
500 500 599667 6789868 77772751 100000 439 32 175 435 407 164 144 186 488 154 129 72 316 0 76 388 427 38 326 66 414 271 487 274 492 351 377 56 279 280 386 378 67 16 356 46 177 334 298 160 192 158 301 331 470 487 418 19 384 112 16 462 466 83 60 240 405 45 16 500 120 236 258 331 489 65 500 34 133 145 ...
output:
432137800
result:
ok single line: '432137800'
Test #33:
score: 65
Accepted
time: 313ms
memory: 121668kb
input:
500 500 1221556 225677 999999999 900 0 0 77 78 182 182 49 48 362 364 384 384 247 246 203 203 235 237 363 365 135 135 84 85 221 220 282 280 245 245 114 116 125 123 357 356 173 173 25 26 166 167 296 298 198 199 470 472 83 83 179 179 340 339 447 446 339 337 179 177 220 220 332 332 298 300 90 90 300 302...
output:
156104617647
result:
ok single line: '156104617647'
Test #34:
score: 65
Accepted
time: 361ms
memory: 128388kb
input:
500 500 14775646 3458867 586774635 1500 237 243 240 232 390 183 91 413 336 183 302 485 136 177 374 390 238 94 459 463 134 423 274 175 143 488 420 89 101 143 343 115 75 470 59 261 465 468 228 482 322 133 85 385 36 283 254 131 280 15 182 232 36 283 348 332 346 294 126 149 318 161 245 189 82 267 299 48...
output:
4786954321
result:
ok single line: '4786954321'
Test #35:
score: 65
Accepted
time: 173ms
memory: 121876kb
input:
500 500 1000000000 10000000 1000000000 100000 119 126 254 235 447 108 158 8 36 209 96 374 366 383 249 158 216 41 456 376 288 101 241 51 203 69 477 489 114 408 476 458 89 252 467 463 174 375 215 434 201 288 68 86 287 357 174 180 389 109 360 134 323 159 57 321 236 17 57 24 287 419 262 337 333 235 236 ...
output:
525000000000
result:
ok single line: '525000000000'
Extra Test:
score: 0
Extra Test Passed