#include <bits/stdc++.h>
#define ll long long
using namespace std;
unordered_set<ll>& sUnion(unordered_set<ll>& a, unordered_set<ll>& b, ll one, ll two) {
if (a.size() > b.size()) {
for (ll elem : b) a.insert(elem);
a.erase(one);
a.erase(two);
return a;
}
for (ll elem : a) b.insert(elem);
b.erase(one);
b.erase(two);
return b;
}
inline ll combs(ll a) {
return (a - 1) * a;
}
class UnionFind {
public:
vector<ll> root, rank, group;
vector<unordered_set<ll>> dependencies;
UnionFind(ll n) {
root.resize(n);
rank.resize(n);
group.resize(n);
dependencies.resize(n);
for (ll i = 0; i < n; i++) {
root[i] = i;
rank[i] = 1;
group[i] = 1;
}
}
ll find(ll a) {
if (root[a] == a) return a;
return root[a] = find(root[a]);
}
void join(ll a, ll b){
ll roota = find(a), rootb = find(b);
if (roota != rootb) {
if (rank[roota] < rank[rootb]) {
root[roota] = rootb;
group[rootb] += group[roota];
dependencies[rootb] = sUnion(dependencies[roota], dependencies[rootb], a, b);
} else if (rank[rootb] < rank[roota]) {
root[rootb] = roota;
group[roota] += group[rootb];
dependencies[roota] = sUnion(dependencies[roota], dependencies[rootb], a, b);
} else {
root[roota] = rootb;
rank[rootb]++;
group[rootb] += group[roota];
dependencies[rootb] = sUnion(dependencies[roota], dependencies[rootb], a, b);
}
}
}
inline bool connected(ll a, ll b) {
return find(a) == find(b);
}
inline ll getg(ll a) {
return group[find(a)];
}
inline ll getd(ll a) {
return dependencies[find(a)].size();
}
inline void updd(ll a, ll val) {
dependencies[find(a)].insert(val);
}
};
int main() {
ll n, m, i, a, b, ans = 0;
queue<ll> todel;
cin >> n >> m;
vector<unordered_set<ll>> isfollowing(n + 1);
UnionFind uf(n + 1);
vector<vector<ll>> queries(m, vector<ll>(2));
for (i = 0; i < m; i++) cin >> queries[i][0] >> queries[i][1];
for (i = 0; i < m; i++) {
a = queries[i][0];
b = queries[i][1];
if (isfollowing[b].find(a) == isfollowing[b].end()) {
ans -= uf.getd(b) * uf.getg(b);
uf.updd(b, a);
ans += uf.getd(b) * uf.getg(b);
} else {
ans -= combs(uf.getg(a));
ans -= combs(uf.getg(b));
ans -= uf.getd(a) * uf.getg(a);
ans -= uf.getd(b) * uf.getg(b);
uf.join(a, b);
ans += combs(uf.getg(a));
ans += uf.getd(a) * uf.getg(a);
}
isfollowing[a].insert(b);
cout << ans << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
