#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
set<int> adj[100000];
set<P> rev[100000];
int p[100000];
int n,m;
set<P> edge;
int find(int a) {
if (p[a]<0) {
return a;
}
return p[a]=find(p[a]);
}
void merge(int a,int b) {
a=find(a);
b=find(b);
if (a==b) {
return;
}
p[a]+=p[b];
p[b]=a;
}
long long func(int x) {
return (1LL*x*(x-1));
}
int main(void) {
scanf("%d %d",&n,&m);
long long ret=0;
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
int a,b;
scanf("%d %d",&a,&b);
a--;
b--;
if (find(a)==find(b)||adj[a].find(find(b))!=adj[a].end()) {
printf("%lld\n",ret);
continue;
}
if (edge.find(P(b,a))==edge.end()) {
adj[a].insert(b);
rev[b].insert(P(find(a),a));
edge.insert(P(a,b));
ret+=-p[b];
}
else {
a=find(a);
b=find(b);
ret+=(-p[b])*(rev[a].size()-distance(rev[a].lower_bound(P(b+1,-1)),rev[a].lower_bound(P(b,-1))));
ret+=(-p[a])*(rev[b].size()-distance(rev[b].lower_bound(P(a+1,-1)),rev[b].lower_bound(P(a,-1))));
ret-=-p[a]*(distance(rev[a].lower_bound(P(b+1,-1)),rev[a].lower_bound(P(b,-1))));
ret-=-p[b]*(distance(rev[b].lower_bound(P(a+1,-1)),rev[b].lower_bound(P(a,-1))));
ret-=func(-p[a]);
ret-=func(-p[b]);
ret+=func(-p[a]-p[b]);
if (rev[a].size()-1>rev[b].size()) {
for(auto curr:rev[b]) {
if (curr.first!=a) {
rev[a].insert(curr);
adj[curr.second].erase(b);
adj[curr.second].insert(a);
}
}
merge(a,b);
}
else {
for(auto curr:rev[a]) {
if (curr.first!=b) {
rev[b].insert(curr);
adj[curr.second].erase(a);
adj[curr.second].insert(b);
}
}
merge(b,a);
}
auto iter=rev[a].lower_bound(P(b,-1));
while (iter!=rev[a].end()) {
if ((*iter).first!=b) {
break;
}
adj[(*iter).second].erase(a);
rev[a].erase(iter);
iter++;
}
auto iter2=rev[b].lower_bound(P(a,-1));
while (iter2!=rev[b].end()) {
if ((*iter2).first!=a) {
break;
}
adj[(*iter2).second].erase(b);
rev[b].erase(iter2);
iter2++;
}
}
printf("%lld\n",ret);
}
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d %d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5016 ms |
10064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5016 ms |
10064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5016 ms |
10064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
