QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461296#6354. 4grass8cowWA 0ms11900kbC++17966b2024-07-02 17:31:522024-07-02 17:31:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-02 17:31:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11900kb
  • [2024-07-02 17:31:52]
  • 提交

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'