#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5;
int p[mxN];
int ssize[mxN];
vector<set<pair<int,int>>> ain(mxN);
vector<set<pair<int,int>>> aout(mxN);
long long int res = 0;
void upd(int a){
while (p[p[a]] != p[a]){
p[a] = p[p[a]];
}
}
void comb(int a, int b){
if (ssize[a] > ssize[b]){
swap(a,b);
}
res += (long long int) ssize[a] * ssize[b]*2;
/* cout << a <<';' << b << ' ' << res << ' ' << ssize[a] << " " << ssize[b] << '\n';
cout << "a: ";
for (auto it = aout[a].begin(); it != aout[a].end(); it++){
cout << (*it).first << "," << (*it).second << " ";
}
cout << '\n';
for (auto it = ain[a].begin(); it != ain[a].end(); it++){
cout << (*it).first << "," << (*it).second << ' ';
}
cout << '\n';
cout << "b: \n";
for (auto it = aout[b].begin(); it != aout[b].end(); it++){
cout << (*it).first << "," << (*it).second << " ";
}
cout << '\n';
for (auto it = ain[b].begin(); it != ain[b].end(); it++){
cout << (*it).first << "," << (*it).second << " ";
}
cout << "\n\n";*/
auto it = aout[b].lower_bound({a,-1});
while (it != aout[b].end()){
upd((*it).first);
if (p[(*it).first] != a){
break;
}
res -= ssize[a];
auto it2 = it;
it++;
aout[b].erase(it2);
}
// cout << "HRE\n";
it = ain[b].lower_bound({a,-1});
while (it != ain[b].end()){
upd((*it).first);
if (p[(*it).first] != a){
break;
}
auto it2 = it;
it++;
ain[b].erase(it2);
}
res -= ssize[b] * (long long int) ain[b].size();
//cout << "HRERE2\n";
for (auto it = aout[a].begin(); it != aout[a].end(); it++){
upd((*it).first);
if (p[(*it).first] == b){
res -= ssize[b];
continue;
}
aout[b].insert((*it));
}
// cout<< "HERERER3\n";
for (auto it = ain[a].begin(); it != ain[a].end(); it++){
upd((*it).first);
if (p[(*it).first] == b){
continue;
}
res -= ssize[a];
ain[b].insert(*it);
}
// cout << "H4\n";
p[a] = b;
ssize[b] += ssize[a];
res += ssize[b] * (long long int) ain[b].size();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
for (int i =0; i < n; i++){
p[i] = i;
ssize[i] = 1;
}
int a,b;
for (int i = 0; i < m; i++){
cin >> a >> b;
a -= 1;
b -= 1;
upd(a);
upd(b);
if (p[a] == p[b]){
cout << res << '\n';
continue;
}
auto it = aout[p[a]].find({p[b],a});
if (it != aout[p[a]].end()){
cout << res << '\n';
continue;
}
// cout << "TEMp " << res << '\n';
res += ssize[p[b]];
aout[p[a]].insert({p[b],a});
ain[p[b]].insert({p[a],a});
it = ain[p[a]].lower_bound({p[b],-1});
if (it != ain[p[a]].end() && (*it).first == p[b]){
comb(p[a],p[b]);
}
cout << res << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
