QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326516#6354. 4KalenistWA 2ms12588kbC++141.7kb2024-02-13 12:21:412024-02-13 12:21:41

Judging History

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

  • [2024-02-13 12:21:41]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12588kb
  • [2024-02-13 12:21:41]
  • 提交

answer

#include<bits/stdc++.h>
#define N 100010
#define ull unsigned long long
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define pc __builtin_popcountll
using namespace std;
int n,m,d[N],rnk[N];
long long ans;
struct E{int x,y;}nw[N*400];
vector<int> go[N],e[N];
struct my_bitset
{
    int sz;ull v[10];
    inline void ins(int x){v[x/64]|=1ull<<(x%64);}
    inline void init(int nsz)
    {
        sz=(nsz-1)/64;
        For(i,0,sz) v[i]=0;
    }
    inline int cnt()
    {
        int res=0;
        For(i,0,sz) res+=pc(v[i]);
        return res;
    }
    inline my_bitset operator &(const my_bitset &p)const
    {
        my_bitset res;res.sz=sz;
        For(i,0,sz) res.v[i]=v[i]&p.v[i];
        return res;
    }
}bs[1010];

inline int read()
{
    register int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

int main()
{
    n=read(),m=read();
    For(i,1,m)
    {
        int x=read(),y=read();
        d[x]++,go[x].push_back(y);
        d[y]++,go[y].push_back(x);
    }
    For(i,1,n) for(int to:go[i])
        if(d[i] < d[to] || d[i] == d[to] && i < to)
            e[i].push_back(to);
    For(i,1,n)
    {
        int cnt=0,sz=e[i].size();rnk[0]=0;
        for(int to:e[i]) rnk[to]=++rnk[0],bs[rnk[0]].init(sz);
        for(int to:e[i]) for(int v:e[to])
            if(rnk[to]) bs[rnk[to]].ins(rnk[v]-1),nw[++cnt]=(E){to,v};
        For(j,1,cnt)
        {
            int a=nw[j].x,b=nw[j].y;
            ans+=(bs[rnk[a]]&bs[rnk[b]]).cnt();
        }for(int to:e[i]) rnk[to]=0;
    }printf("%lld\n",ans);
    return 0;
}
/*
5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12184kb

input:

5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 10188kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 2ms
memory: 10048kb

input:

50 50
28 35
12 24
31 50
10 24
21 44
5 31
23 36
31 45
6 39
4 8
13 37
42 48
17 45
19 33
12 21
19 32
16 43
12 47
25 31
40 48
8 49
43 48
6 42
27 34
13 39
17 40
13 35
3 49
20 24
5 12
43 44
15 37
24 27
8 43
4 22
17 38
28 47
29 46
3 15
9 49
1 41
43 45
3 6
37 48
13 30
11 43
8 25
33 38
16 32
32 41

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 12588kb

input:

100 4900
64 78
3 13
93 96
48 64
34 64
5 76
66 74
44 78
17 20
30 73
5 34
24 100
23 65
4 70
22 95
47 70
6 89
15 70
70 82
88 90
29 80
27 64
16 59
28 99
67 68
85 99
37 85
8 46
71 78
40 95
6 21
27 66
16 89
11 83
17 57
19 36
21 70
27 86
27 45
5 56
10 64
23 33
87 91
37 40
21 55
75 79
54 96
3 77
70 78
36 93...

output:

3696062

result:

wrong answer 1st numbers differ - expected: '3689634', found: '3696062'