QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #528551 | #6441. Ancient Magic Circle in Teyvat | sio_ | WA | 3ms | 22352kb | C++14 | 2.1kb | 2024-08-23 16:10:47 | 2024-08-23 16:10:47 |
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)*(n-2)*(n-3)/2/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<=m;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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 21692kb
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: 0ms
memory: 12896kb
input:
4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 20764kb
input:
4 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 22352kb
input:
4 2 1 2 1 3
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 19548kb
input:
4 2 1 2 3 4
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 3ms
memory: 20128kb
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: 20612kb
input:
4 3 1 2 2 3 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 3ms
memory: 22204kb
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: 20604kb
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: 3ms
memory: 20024kb
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: 21176kb
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: 3ms
memory: 22272kb
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: 2ms
memory: 13916kb
input:
633 0
output:
6626427570
result:
ok 1 number(s): "6626427570"
Test #14:
score: -100
Wrong Answer
time: 3ms
memory: 20804kb
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:
6606576790
result:
wrong answer 1st numbers differ - expected: '6606576764', found: '6606576790'