QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461296 | #6354. 4 | grass8cow | WA | 0ms | 11900kb | C++17 | 966b | 2024-07-02 17:31:52 | 2024-07-02 17:31:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int B=450,N=2e5+10;
bitset<B>a[B];
int U[N],V[N];
#define pb push_back
int is[N],rk[N],d[N],be[N];
vector<int>g[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)be[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d",&U[i],&V[i]),d[U[i]]++,d[V[i]]++;
sort(be+1,be+n+1,[&](int x,int y){if(d[x]!=d[y])return d[x]<d[y];return x<y;});
for(int i=1;i<=n;i++)rk[be[i]]=i;
for(int i=1;i<=m;i++){
if(rk[U[i]]>rk[V[i]])swap(U[i],V[i]);
g[U[i]].pb(V[i]);
}
long long ans=0;
for(int i=1;i<=n;i++){
int o=0;
for(int v:g[i])is[v]=++o;
for(int j=1;j<=o;j++)a[j].reset();
for(int v:g[i])for(int w:g[v])if(is[w])a[is[v]][is[w]]=a[is[w]][is[v]]=1;
for(int v:g[i])for(int w:g[v])if(is[w])ans+=(a[is[v]]&a[is[w]]).count();
for(int v:g[i])is[v]=0;
}
printf("%lld",ans/2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 11900kb
input:
5 9 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5
output:
3
result:
wrong answer 1st numbers differ - expected: '2', found: '3'