#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 1000001;
set <int> in[nmax], out[nmax];
set <int> indg[nmax];
ll sz[nmax];
ll curans;
int p[nmax];
vector <vector <int> > cmp(nmax);
int find_set(int a){
return p[a] == a ? a : p[a] = find_set(p[a]);
}
void union_sets(int a, int b){
if(a == b)
return;
if(sz[a] < sz[b])
swap(a, b);
curans -= (ll)indg[b].size() * sz[b];
curans -= (ll)indg[a].size() * sz[a];
curans -= sz[b] * sz[b] - sz[b];
curans -= sz[a] * sz[a] - sz[a];
// cout << curans << ' ';
vector <int> vec;
out[b].erase(a);
out[a].erase(b);
in[a].erase(b);
in[b].erase(a);
for(int to : out[b]){
if(in[a].find(to) != in[a].end())
vec.pb(to);
out[a].insert(to);
}
for(int to : in[b]){
if(out[a].find(to) != out[a].end())
vec.pb(to);
in[a].insert(to);
}
for(int to : indg[b]){
if(find_set(to) != a) indg[a].insert(to);
}
for(int to : cmp[b]){
cmp[a].pb(to);
indg[a].erase(to);
}
p[b] = a;
sz[a] += sz[b];
curans += sz[a] * indg[a].size();
// cout << curans << ' ';
curans += sz[a] * sz[a] - sz[a];
for(int to : vec){
union_sets(a, to);
}
}
void Merge(int a, int b){
b = find_set(b);
int x= find_set(a);
if(in[x].find(b) != in[x].end()){
union_sets(x, b);
}
else{
curans -= sz[b] * (ll)indg[b].size();
indg[b].insert(a);
curans += sz[b] * (ll)indg[b].size();
in[b].insert(x);
out[x].insert(b);
}
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++){
p[i] = i;
sz[i] = 1;
cmp[i].pb(i);
}
int m; cin >> m;
for(int i= 1; i <= m; i++){
int u, v; cin >> u >> v;
Merge(u, v);
cout << curans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
164644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
164644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
164644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
