QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326516 | #6354. 4 | Kalenist | WA | 2ms | 12588kb | C++14 | 1.7kb | 2024-02-13 12:21:41 | 2024-02-13 12:21:41 |
Judging History
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'