#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define int ll
typedef pair<int, int> pii;
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define inf LLONG_MAX/2
#define ff first
#define ss second
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define last(s) (*--s.end())
#define first(s) *s.begin()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
vector<int> par;
vector<set<int>> to, pfrom, comp;
int res = 0;
int find(int a){
while(par[a] >= 0) a = par[a];
return a;
}
void uni(int a, int b){
a = find(a);
b = find(b);
if(-par[a] < -par[b]) swap(a, b);
res -= (-par[a]) * ((-par[a]) - 1);
res -= (-par[b]) * ((-par[b]) - 1);
res -= to[a].size() * (-par[a]);
res -= to[b].size() * (-par[b]);
par[a] += par[b];
for (auto f : to[b]){
if(comp[a].find(f) == comp[a].end()) to[a].insert(f);
int pf = find(f);
pfrom[pf].erase(b);
pfrom[pf].insert(a);
}
to[b].clear();
for (auto f : comp[b]) {
comp[a].insert(f);
to[a].erase(f);
}
comp[b].clear();
for (auto f : pfrom[b]) {
pfrom[a].insert(f);
}
pfrom[b].clear();
par[b] = a;
res += (-par[a]) * ((-par[a]) - 1);
res += to[a].size() * (-par[a]);
}
signed main()
{
int n, m; cin >> n >> m;
par.assign(n, -1);
to.assign(n, {});
pfrom.assign(n, {});
comp.assign(n, {});
FOR(i, n) comp[i].insert(i);
while(m--){
int a, b; cin >> a >> b; a--; b--; // a -> b
int pa = find(a), pb = find(b);
if(pa == pb) continue;
if(pfrom[pb].find(pa) != pfrom[pb].end()){
uni(a, b);
}
else{
if(to[pb].find(a) == to[pb].end()){
to[pb].insert(a);
pfrom[pa].insert(pb);
res += (-par[pb]);
}
}
cout << res << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
