QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #528568 | #6441. Ancient Magic Circle in Teyvat | sio_ | WA | 803ms | 32896kb | C++14 | 2.1kb | 2024-08-23 16:23:14 | 2024-08-23 16:23:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
int n,m,u[maxn],v[maxn],d[maxn],vis[maxn];
int cnt[maxn],pcnt[maxn];
vector<pair<int,int>> nbr[maxn];
vector<int> V[maxn];
int ans,res3,res4;
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>u[i]>>v[i],d[u[i]]++,d[v[i]]++;
ans=n*(n-1)/2*(n-2)/3*(n-3)/4;
ans-=m*(n-2)*(n-3)/2;
for(int i=1;i<=n;i++) ans+=d[i]*(d[i]-1)/2*(n-3);
ans+=m*(m-1)/2;
for(int i=1;i<=n;i++) ans-=d[i]*(d[i]-1)/2;
for(int i=1;i<=n;i++) ans-=d[i]*(d[i]-1)*(d[i]-2)/2/3;
for(int i=1;i<=m;i++)
{
if(d[u[i]]<d[v[i]]||(d[u[i]]==d[v[i]]&&u[i]<v[i])) nbr[u[i]].push_back({v[i],i});
else nbr[v[i]].push_back({u[i],i});
V[v[i]].push_back(u[i]);
V[u[i]].push_back(v[i]);
}
for(int x=1;x<=n;x++)
{
for(int i=0;i<nbr[x].size();i++) vis[nbr[x][i].first]=nbr[x][i].second;
for(int i=0;i<nbr[x].size();i++)
{
int y=nbr[x][i].first;
for(int j=0;j<nbr[y].size();j++)
{
int z=nbr[y][j].first;
if(vis[z]==0) continue;
cnt[nbr[x][i].second]++,cnt[nbr[y][j].second]++,cnt[vis[z]]++;
pcnt[x]++,pcnt[y]++,pcnt[z]++;
res3++;
}
}
for(int i=0;i<nbr[x].size();i++) vis[nbr[x][i].first]=0;
}
ans-=(n-3)*res3;
for(int i=1;i<=m;i++) ans-=(d[u[i]]-1)*(d[v[i]]-1);
ans+=3*res3;
for(int i=1;i<=n;i++) ans+=pcnt[i]*(d[i]-2);
for(int i=1;i<=m;i++) ans-=cnt[i]*(cnt[i]-1)/2;
for(int x=1;x<=n;x++)
{
for(int i=0;i<V[x].size();i++)
{
int y=V[x][i];
for(int j=0;j<nbr[y].size();j++)
{
int z=nbr[y][j].first;
if(d[x]<d[z]||(d[x]==d[z]&&x<z)) res4+=vis[z],vis[z]++;
}
}
for(int i=0;i<V[x].size();i++)
{
int y=V[x][i];
for(int j=0;j<nbr[y].size();j++) vis[nbr[y][j].first]=0;
}
}
ans+=res4;
cout<<abs(ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 21416kb
input:
7 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 3ms
memory: 14620kb
input:
4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 19748kb
input:
4 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 20340kb
input:
4 2 1 2 1 3
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 20044kb
input:
4 2 1 2 3 4
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 19692kb
input:
4 3 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 19232kb
input:
4 3 1 2 2 3 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 0ms
memory: 20596kb
input:
4 3 1 2 2 3 1 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 0ms
memory: 21212kb
input:
4 4 1 2 2 3 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 20188kb
input:
4 4 1 2 2 3 3 4 1 4
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 3ms
memory: 22312kb
input:
4 5 1 2 1 3 1 4 2 3 3 4
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 0ms
memory: 20476kb
input:
4 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 3ms
memory: 13060kb
input:
633 0
output:
6626427570
result:
ok 1 number(s): "6626427570"
Test #14:
score: 0
Accepted
time: 0ms
memory: 19664kb
input:
633 100 284 424 27 560 19 484 92 558 59 385 440 577 11 420 341 543 285 330 430 569 88 259 13 499 444 557 418 483 167 220 185 497 175 489 246 400 387 577 125 303 99 336 152 437 116 324 229 472 200 338 46 197 368 399 345 386 92 439 121 132 50 310 444 525 454 631 174 337 276 337 476 597 405 557 99 263 ...
output:
6606576764
result:
ok 1 number(s): "6606576764"
Test #15:
score: 0
Accepted
time: 4ms
memory: 20164kb
input:
633 200 147 540 247 463 502 553 168 519 24 395 126 170 417 437 77 94 453 466 104 400 32 145 231 496 199 360 391 597 492 599 526 627 384 481 219 238 115 508 74 112 239 243 96 480 31 164 119 467 96 578 275 574 66 364 80 409 18 527 97 462 552 570 7 350 344 473 221 621 174 613 167 181 61 474 45 320 64 4...
output:
6586769859
result:
ok 1 number(s): "6586769859"
Test #16:
score: 0
Accepted
time: 0ms
memory: 19760kb
input:
633 500 193 462 116 450 462 486 197 295 471 593 189 220 484 576 143 415 256 588 132 543 46 363 18 184 105 395 243 529 36 188 83 588 127 339 184 415 182 193 123 341 176 427 446 484 143 525 76 473 161 519 126 386 234 418 119 181 28 94 543 569 333 448 206 588 103 563 499 536 131 263 614 632 478 489 284...
output:
6527638886
result:
ok 1 number(s): "6527638886"
Test #17:
score: 0
Accepted
time: 0ms
memory: 21844kb
input:
633 1000 213 614 307 555 146 543 262 297 35 351 99 562 92 222 270 390 102 483 591 597 358 543 40 129 157 466 134 438 288 456 49 535 250 316 24 536 93 585 341 550 66 110 185 330 146 434 131 496 68 413 414 625 4 96 19 460 5 444 35 589 118 245 30 387 249 325 65 390 177 572 216 499 309 608 155 486 509 6...
output:
6430135035
result:
ok 1 number(s): "6430135035"
Test #18:
score: 0
Accepted
time: 0ms
memory: 22204kb
input:
633 2000 37 314 132 319 127 409 37 579 573 594 107 149 144 337 108 618 259 515 6 596 145 201 152 263 488 512 290 294 542 578 157 311 577 590 517 536 529 539 61 260 100 374 224 626 479 564 36 548 46 242 190 592 27 88 30 181 125 351 17 604 214 428 255 388 90 201 126 430 109 384 238 534 191 197 160 502...
output:
6238668674
result:
ok 1 number(s): "6238668674"
Test #19:
score: 0
Accepted
time: 3ms
memory: 20868kb
input:
633 5000 151 587 351 429 271 387 271 398 213 560 167 483 531 596 79 260 532 571 167 179 158 623 26 194 450 515 346 583 30 217 316 551 27 234 208 449 272 397 50 318 105 229 458 526 145 301 17 306 114 159 163 177 169 608 61 211 204 477 43 311 109 509 535 539 78 588 177 280 64 142 305 593 418 444 453 5...
output:
5692706944
result:
ok 1 number(s): "5692706944"
Test #20:
score: 0
Accepted
time: 6ms
memory: 21876kb
input:
633 10000 44 377 191 460 198 226 32 599 312 406 414 564 52 508 203 319 319 376 428 629 99 589 53 228 586 590 21 443 12 155 25 400 147 369 27 374 394 489 118 548 70 397 242 278 245 257 509 522 82 372 39 233 182 264 246 588 511 570 349 418 168 339 137 615 419 420 66 461 182 462 260 538 4 604 99 494 15...
output:
4870867167
result:
ok 1 number(s): "4870867167"
Test #21:
score: 0
Accepted
time: 13ms
memory: 22512kb
input:
633 20000 25 130 270 612 2 361 228 277 106 138 45 207 12 291 36 450 336 589 293 586 7 331 13 94 182 244 21 293 109 446 142 406 311 439 68 423 372 383 172 453 283 311 196 438 249 400 391 562 232 538 539 553 357 607 24 257 171 336 422 430 472 576 47 501 531 574 72 237 14 428 56 163 386 592 220 627 62 ...
output:
3521002107
result:
ok 1 number(s): "3521002107"
Test #22:
score: 0
Accepted
time: 48ms
memory: 24024kb
input:
633 50000 5 605 325 341 407 507 349 401 369 461 70 297 228 518 241 244 58 563 59 459 153 480 101 606 13 140 312 336 396 456 307 607 94 413 129 340 21 456 153 452 419 575 322 411 313 617 160 310 426 430 444 594 214 335 33 175 32 41 257 540 424 462 39 582 181 190 62 238 50 262 181 269 22 289 251 331 6...
output:
1177969809
result:
ok 1 number(s): "1177969809"
Test #23:
score: 0
Accepted
time: 142ms
memory: 26348kb
input:
633 80000 234 361 181 425 481 538 145 313 188 308 69 423 250 607 192 320 472 626 119 219 361 612 186 191 52 144 28 320 238 472 206 439 318 445 252 341 10 517 376 442 209 213 82 181 69 458 224 487 494 624 207 395 183 621 487 599 166 213 245 490 45 292 131 592 175 544 2 464 62 468 7 332 336 420 277 56...
output:
282030903
result:
ok 1 number(s): "282030903"
Test #24:
score: 0
Accepted
time: 174ms
memory: 26100kb
input:
633 90000 271 596 308 446 104 300 269 632 434 537 101 609 47 239 32 565 232 468 171 477 128 575 206 352 459 563 8 252 203 546 135 549 23 389 252 261 17 215 23 581 130 429 332 577 461 536 429 520 415 540 250 577 51 583 475 625 299 592 208 372 47 442 170 425 183 187 184 512 103 277 463 540 32 310 169 ...
output:
128519898
result:
ok 1 number(s): "128519898"
Test #25:
score: 0
Accepted
time: 215ms
memory: 26808kb
input:
633 100000 100 486 30 184 85 561 22 569 22 517 89 461 61 369 178 324 178 255 281 414 295 553 492 506 14 351 63 202 44 222 64 86 64 598 7 28 191 343 592 620 303 502 46 427 383 614 593 632 278 479 35 631 264 373 95 561 215 279 290 370 201 206 179 533 322 602 138 149 373 569 7 302 163 566 93 276 374 47...
output:
38486
result:
ok 1 number(s): "38486"
Test #26:
score: 0
Accepted
time: 250ms
memory: 27256kb
input:
633 110000 22 203 608 632 35 555 42 237 264 608 157 266 206 578 92 568 18 93 245 427 601 618 10 443 137 214 121 243 342 601 46 344 112 132 35 427 252 313 11 547 394 565 389 391 161 246 352 417 224 525 122 201 508 561 488 628 82 218 99 136 70 250 271 321 69 337 560 588 166 579 92 554 68 583 169 414 9...
output:
128079474
result:
ok 1 number(s): "128079474"
Test #27:
score: 0
Accepted
time: 297ms
memory: 27676kb
input:
633 120000 185 542 7 14 27 592 224 569 98 352 448 543 105 123 134 210 91 413 93 393 29 132 283 501 190 275 380 603 103 557 449 489 44 623 2 551 43 573 547 579 52 354 97 378 309 502 147 405 57 375 98 488 195 522 3 6 224 411 163 577 213 368 197 260 140 341 13 578 19 510 155 603 447 501 93 476 250 340 ...
output:
281577985
result:
ok 1 number(s): "281577985"
Test #28:
score: 0
Accepted
time: 434ms
memory: 28316kb
input:
633 150000 592 604 140 354 185 631 165 483 349 356 539 609 113 115 240 398 426 576 53 200 353 378 416 534 228 427 117 327 140 410 66 324 180 432 442 568 175 546 50 145 171 528 81 447 47 327 258 377 225 568 475 489 136 449 29 548 568 630 238 321 278 468 526 629 81 123 324 372 310 339 298 523 446 489 ...
output:
1176277456
result:
ok 1 number(s): "1176277456"
Test #29:
score: 0
Accepted
time: 589ms
memory: 31736kb
input:
633 180000 387 421 280 528 273 412 212 561 1 582 219 457 190 503 464 605 56 625 223 240 87 146 178 335 456 624 311 353 108 273 349 601 384 544 91 240 172 549 21 58 439 479 62 157 102 428 374 575 469 473 173 181 97 448 209 225 132 440 116 591 348 412 40 225 440 507 155 611 7 361 211 550 105 369 469 6...
output:
3518581095
result:
ok 1 number(s): "3518581095"
Test #30:
score: 0
Accepted
time: 670ms
memory: 32464kb
input:
633 190000 11 536 414 607 96 155 390 561 403 474 100 629 56 92 464 472 410 618 329 474 153 169 520 543 192 314 173 509 422 465 75 131 449 567 97 254 195 276 286 511 67 573 3 216 82 198 283 593 94 267 149 429 58 449 70 546 248 575 194 248 244 482 133 607 439 577 267 316 63 228 400 419 469 540 19 469 ...
output:
4866760887
result:
ok 1 number(s): "4866760887"
Test #31:
score: 0
Accepted
time: 714ms
memory: 32576kb
input:
633 195000 348 436 145 467 483 526 226 347 13 106 448 534 267 508 533 615 466 551 40 128 382 589 150 293 207 225 312 589 307 373 39 525 108 191 154 211 155 223 334 485 121 561 14 479 335 590 401 464 24 327 183 440 423 628 226 615 10 298 504 602 552 597 124 558 311 549 47 537 85 632 176 364 405 528 3...
output:
5687918187
result:
ok 1 number(s): "5687918187"
Test #32:
score: 0
Accepted
time: 752ms
memory: 32632kb
input:
633 198000 221 331 330 409 172 587 132 161 157 283 139 437 225 562 314 573 50 250 242 603 454 514 248 466 402 535 27 606 32 365 189 452 166 427 75 78 11 301 553 618 195 589 399 434 406 432 20 29 576 594 381 444 8 629 426 595 404 430 545 557 382 469 277 596 282 406 160 368 362 388 237 443 83 514 359 ...
output:
6233483213
result:
ok 1 number(s): "6233483213"
Test #33:
score: 0
Accepted
time: 782ms
memory: 32648kb
input:
633 199000 77 409 18 73 36 132 78 571 53 515 64 147 495 498 69 289 235 620 159 326 15 596 203 617 520 541 231 246 8 519 542 568 120 585 338 421 283 622 327 372 155 289 198 590 507 584 347 473 91 390 176 481 362 401 484 595 44 298 114 433 403 476 327 480 176 488 217 349 18 198 514 546 126 528 435 469...
output:
6424675566
result:
ok 1 number(s): "6424675566"
Test #34:
score: 0
Accepted
time: 803ms
memory: 32784kb
input:
633 199500 512 543 136 386 4 600 95 598 241 506 178 527 72 453 353 378 341 417 294 321 26 604 185 514 253 414 368 476 152 326 320 418 82 429 226 365 383 527 303 607 501 593 185 531 262 515 344 509 4 38 196 438 391 547 321 623 24 28 322 339 393 631 38 520 244 500 18 173 300 382 62 134 24 157 129 190 ...
output:
6522157271
result:
ok 1 number(s): "6522157271"
Test #35:
score: 0
Accepted
time: 751ms
memory: 32896kb
input:
633 199800 191 583 72 157 357 539 103 358 293 582 19 84 314 445 62 388 195 524 29 366 227 600 158 510 378 588 250 380 234 544 114 524 39 337 462 486 230 632 235 242 74 272 208 447 51 239 367 531 309 461 6 224 134 244 329 520 128 351 224 555 245 516 370 586 229 447 336 519 304 630 235 628 405 480 3 3...
output:
6581228607
result:
ok 1 number(s): "6581228607"
Test #36:
score: 0
Accepted
time: 667ms
memory: 32796kb
input:
633 199900 42 520 108 550 129 489 250 392 293 485 257 311 450 471 288 388 572 599 209 282 32 521 239 328 301 564 76 107 23 374 125 506 57 321 122 240 365 380 138 587 317 364 55 331 410 594 154 441 441 546 183 495 390 564 61 351 244 543 418 538 365 426 4 237 105 291 157 505 432 484 113 595 179 278 45...
output:
6601027717
result:
ok 1 number(s): "6601027717"
Test #37:
score: 0
Accepted
time: 621ms
memory: 32644kb
input:
633 200000 152 218 163 263 349 518 482 568 27 476 235 532 58 229 334 338 249 327 171 337 150 477 201 583 438 601 449 512 160 470 535 589 294 620 344 617 519 588 254 422 79 506 28 47 268 543 185 226 37 68 66 172 92 210 358 459 13 546 176 384 233 462 200 563 581 612 332 362 2 394 323 605 176 521 13 29...
output:
6620862528
result:
ok 1 number(s): "6620862528"
Test #38:
score: -100
Wrong Answer
time: 702ms
memory: 32732kb
input:
100000 200000 21414 38956 23290 37981 22420 43565 29518 86702 39041 69075 18922 22263 29518 91286 16526 87951 32319 37127 37289 79294 14890 70945 74535 79294 1188 89898 16768 89742 6825 41001 29490 92496 26840 55489 76921 99018 1496 34503 43045 65599 14273 26688 34369 63201 55489 88446 53799 85460 2...
output:
446260911180575683
result:
wrong answer 1st numbers differ - expected: '4165425107246812221', found: '446260911180575683'