QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #528561 | #6441. Ancient Magic Circle in Teyvat | sio_ | WA | 4ms | 22148kb | C++14 | 2.1kb | 2024-08-23 16:18:29 | 2024-08-23 16:18:29 |
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<=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);
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 22148kb
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: 14552kb
input:
4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 19476kb
input:
4 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 4ms
memory: 19672kb
input:
4 2 1 2 1 3
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 19096kb
input:
4 2 1 2 3 4
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 21108kb
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: 20536kb
input:
4 3 1 2 2 3 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 4ms
memory: 21224kb
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: 21148kb
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: 19916kb
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: 0ms
memory: 21064kb
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: 20788kb
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: 13920kb
input:
633 0
output:
6626427570
result:
ok 1 number(s): "6626427570"
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 21056kb
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'