#include<cstdio>
#include<vector>
#include<algorithm>
std::vector<int> a[111111];
int p[111111];
int q[111111];
int par(int x){return x==p[x]?x:p[x]=par(p[x]);}
void com(int x,int y)
{
x=par(x);y=par(y);
if(x==y)return;
p[x]=y;q[y]+=q[x];
int i;
for(i=0;i<a[x].size();i++)com(a[x][i],y);
for(i=0;i<a[y].size();i++)com(a[y][i],x);
}
int main()
{
long long res;
int i,j,n,m;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&i,&j);
a[i].push_back(j);
}
for(i=1;i<=n;i++)
{
p[i]=i;
q[i]=1;
std::sort(a[i].begin(),a[i].end());
}
for(i=1;i<=n;i++)
{
if(!a[i].empty()&&binary_search(a[a[i][0]].begin(),a[a[i][0]].end(),i))com(a[i][0],i);
for(j=1;j<a[i].size();j++)
{
com(a[i][j],a[i][0]);
if(binary_search(a[a[i][j]].begin(),a[a[i][j]].end(),i))com(a[i][j],i);
}
}
res=0;
for(i=1;i<=n;i++)
{
if(i==p[i])res+=1LL*q[i]*(q[i]-1);
for(j=0;j<a[i].size();j++)if(par(i)!=par(a[i][j]))res++;
}
printf("%lld\n",res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4684 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 5 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 7 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 9 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4684 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 12 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 13 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 14 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 15 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 16 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 17 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4828 KB |
Output is correct |
| 4 |
Correct |
68 ms |
5708 KB |
Output is correct |
| 5 |
Correct |
60 ms |
5440 KB |
Output is correct |
| 6 |
Correct |
93 ms |
6100 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4684 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 9 |
Correct |
13 ms |
4816 KB |
Output is correct |
| 10 |
Correct |
19 ms |
5024 KB |
Output is correct |
| 11 |
Correct |
89 ms |
6100 KB |
Output is correct |
| 12 |
Correct |
9 ms |
4816 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4684 KB |
Output is correct |
| 15 |
Correct |
6 ms |
4684 KB |
Output is correct |
| 16 |
Correct |
17 ms |
4952 KB |
Output is correct |
| 17 |
Correct |
86 ms |
5956 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4816 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4924 KB |
Output is correct |
| 20 |
Correct |
77 ms |
6112 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4684 KB |
Output is correct |
| 22 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 23 |
Correct |
7 ms |
4816 KB |
Output is correct |
| 24 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 25 |
Correct |
2 ms |
4816 KB |
Output is correct |
| 26 |
Correct |
2 ms |
4684 KB |
Output is correct |
| 27 |
Correct |
3 ms |
4816 KB |
Output is correct |
| 28 |
Correct |
2 ms |
4684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
5740 KB |
Output is correct |
| 2 |
Correct |
118 ms |
8560 KB |
Output is correct |
| 3 |
Correct |
132 ms |
8572 KB |
Output is correct |
| 4 |
Correct |
60 ms |
6532 KB |
Output is correct |
| 5 |
Correct |
26 ms |
5872 KB |
Output is correct |
| 6 |
Correct |
118 ms |
7864 KB |
Output is correct |
| 7 |
Correct |
92 ms |
7524 KB |
Output is correct |
| 8 |
Correct |
92 ms |
7456 KB |
Output is correct |
| 9 |
Correct |
60 ms |
6664 KB |
Output is correct |
| 10 |
Correct |
92 ms |
7060 KB |
Output is correct |
| 11 |
Correct |
130 ms |
8580 KB |
Output is correct |
| 12 |
Correct |
108 ms |
9412 KB |
Output is correct |
| 13 |
Correct |
34 ms |
7720 KB |
Output is correct |
| 14 |
Correct |
88 ms |
6440 KB |
Output is correct |
| 15 |
Correct |
19 ms |
5872 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4684 KB |
Output is correct |
| 17 |
Correct |
0 ms |
4684 KB |
Output is correct |
| 18 |
Correct |
109 ms |
7648 KB |
Output is correct |
| 19 |
Correct |
124 ms |
7656 KB |
Output is correct |
| 20 |
Correct |
64 ms |
6268 KB |
Output is correct |
| 21 |
Correct |
34 ms |
5608 KB |
Output is correct |
| 22 |
Correct |
3 ms |
4684 KB |
Output is correct |
| 23 |
Correct |
44 ms |
5408 KB |
Output is correct |
| 24 |
Correct |
69 ms |
6268 KB |
Output is correct |
| 25 |
Correct |
53 ms |
7720 KB |
Output is correct |
| 26 |
Correct |
65 ms |
12284 KB |
Output is correct |
| 27 |
Correct |
116 ms |
10632 KB |
Output is correct |
| 28 |
Correct |
39 ms |
6992 KB |
Output is correct |
| 29 |
Correct |
51 ms |
6964 KB |
Output is correct |
| 30 |
Correct |
107 ms |
8552 KB |
Output is correct |
| 31 |
Correct |
66 ms |
6268 KB |
Output is correct |
| 32 |
Correct |
41 ms |
7720 KB |
Output is correct |
| 33 |
Correct |
42 ms |
7720 KB |
Output is correct |
| 34 |
Correct |
61 ms |
6664 KB |
Output is correct |
| 35 |
Correct |
42 ms |
7720 KB |
Output is correct |
| 36 |
Correct |
43 ms |
10728 KB |
Output is correct |
| 37 |
Correct |
20 ms |
6996 KB |
Output is correct |
