QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#509598 | #6441. Ancient Magic Circle in Teyvat | yyyyxh | WA | 206ms | 13784kb | C++14 | 1.7kb | 2024-08-08 16:27:58 | 2024-08-08 16:27:58 |
Judging History
answer
#include <cstdio>
#include <vector>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003;
typedef long long ll;
typedef __int128 lll;
int n,m;lll res;
void write(lll x){if(x>9) write(x/10);putchar((x%10)^48);}
lll C4(int x){return (lll)x*(x-1)*(x-2)*(x-3)/24;}
lll C3(int x){return (lll)x*(x-1)*(x-2)/6;}
lll C2(int x){return (lll)x*(x-1)>>1;}
int eu[N],ev[N],d[N];
vector<int> adj[N],vec[N],ec[N];
int vis[N],ps[N];
inline bool cmp(int x,int y){
if(d[x]!=d[y]) return d[x]>d[y];
return x<y;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;++i){
eu[i]=read();ev[i]=read();
adj[eu[i]].emplace_back(ev[i]);
adj[ev[i]].emplace_back(eu[i]);
}
for(int i=1;i<=n;++i) d[i]=adj[i].size();
for(int i=1;i<=m;++i)
if(cmp(eu[i],ev[i])) vec[eu[i]].emplace_back(ev[i]);
else vec[ev[i]].emplace_back(eu[i]);
for(int i=1;i<=n;++i) ec[i].resize(vec[i].size());
res=C4(n)-m*C2(n-2);
lll tmp=0;
for(int i=1;i<=m;++i){
int w=d[eu[i]]+d[ev[i]]-2;
tmp+=(lll)w*(n-4);
res-=(lll)(d[eu[i]]-1)*(d[ev[i]]-1);
}
res+=C2(m)+(tmp>>1);
for(int x=1;x<=n;++x){
res-=C3(d[x]);
int id=0;
for(int y:vec[x]) vis[y]=x,ps[y]=id++;
id=0;
for(int y:vec[x]){
int nid=0;
for(int z:vec[y]){
if(vis[z]==x){
res+=d[x]+d[y]+d[z]-n;
res-=ec[x][id]++;
res-=ec[x][ps[z]]++;
res-=ec[y][nid]++;
}
++nid;
}
++id;
}
}
for(int x=1;x<=n;++x){
for(int y:vec[x])
for(int z:adj[y]) vis[z]=0;
for(int y:vec[x])
for(int z:adj[y])
if(cmp(x,z)) res+=vis[z]++;
}
if(res<0) res=-res;
write(res);putchar('\n');
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 10588kb
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: 2ms
memory: 10692kb
input:
4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 10568kb
input:
4 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 11808kb
input:
4 2 1 2 1 3
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 10588kb
input:
4 2 1 2 3 4
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 10760kb
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: 11840kb
input:
4 3 1 2 2 3 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 2ms
memory: 11888kb
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: 10664kb
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: 2ms
memory: 11748kb
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: 2ms
memory: 10596kb
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: 2ms
memory: 10668kb
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: 0ms
memory: 11800kb
input:
633 0
output:
6626427570
result:
ok 1 number(s): "6626427570"
Test #14:
score: 0
Accepted
time: 2ms
memory: 10796kb
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: 2ms
memory: 10684kb
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: 2ms
memory: 11924kb
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: 3ms
memory: 10800kb
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: 3ms
memory: 11808kb
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: 0ms
memory: 10856kb
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: 2ms
memory: 12092kb
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: 11ms
memory: 12204kb
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: 42ms
memory: 12388kb
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: 129ms
memory: 13044kb
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: 163ms
memory: 13492kb
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: 206ms
memory: 13784kb
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: -100
Wrong Answer
time: 3ms
memory: 13300kb
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:
3304966155
result:
wrong answer 1st numbers differ - expected: '128079474', found: '3304966155'