#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
struct ds
{
public:
int N;
vector<int> parent;
vector< vector<int> > members;
vector< set<int> > followers;
long long answer = 0;
ds()
{
;
}
ds(int N_)
{
N = N_;
parent = vector<int>(1+N);
members = vector< vector<int> >(1+N);
followers = vector< set<int> >(1+N);
for(int i = 1; i <= N; i++)
{
parent[i] = i;
members[i].push_back(i);
}
}
int root(int u)
{
if(parent[u] == u) return u;
else
{
parent[u] = root(parent[u]);
return parent[u];
}
}
long long get_score(int u)
{
u = root(u);
long long s = int(members[u].size());
long long f = int(followers[u].size());
return s*(s-1) + s*f;
}
void join(int a, int b)
{
a = root(a);
b = root(b);
if(a == b) return;
answer -= get_score(a);
answer -= get_score(b);
if(int(members[a].size()) < int(members[b].size())) swap(a, b);
parent[b] = a;
for(int m: members[b]) followers[a].erase(m);
for(int f: followers[b])
if(root(f) != a)
followers[a].insert(f);
for(int m: members[b]) members[a].push_back(m);
members[b].clear();
followers[b].clear();
answer += get_score(a);
}
void add_follower(int b, int a)
{
if(root(a) == root(b)) return;
answer -= get_score(b);
followers[root(b)].insert(a);
answer += get_score(b);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
set<int> out_edges[1+N];
ds DSU(N);
for(int j = 1; j <= M; j++)
{
int A, B;
cin >> A >> B;
out_edges[A].insert(B);
DSU.add_follower(B, A);
if(out_edges[B].find(A) != out_edges[B].end())
DSU.join(A, B);
cout << DSU.answer << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
