#include <bits/stdc++.h>
#define ll int
#define ld long double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = INT_MAX;
struct DSU{
struct Vertex{
bool cancel=0;
set<ll> in, out, comp;
ll size(){
return in.size()+out.size()+comp.size();
}
};
ll cnt, sz;
vector<Vertex> a;
vector<ll> p;
DSU(ll N){
a.resize(N+1);
sz=N;
for (ll i=1; i<=sz; i++){
a[i].comp.insert(i);
}
p.resize(N+1, -1);
cnt=0;
}
ll get(ll x){
return p[x]==-1?x:p[x]=get(p[x]);
}
void impact(ll x, ll k = 1){
cnt+=k*(a[x].comp.size()*(a[x].comp.size()-1)+a[x].comp.size()*a[x].in.size());
}
void unite(ll u, ll v){
u = get(u);
v = get(v);
if (u==v) return;
if (a[u].size()<a[v].size()){
swap(u, v);
}
impact(v, -1); impact(u, -1);
for (auto ch:a[v].comp){
a[u].comp.insert(ch);
}
for (auto ch:a[v].in){
a[ch].out.erase(v);
link(ch, u);
}
for (auto ch:a[v].out){
a[ch].in.erase(v);
link(u, ch);
}
impact(u);
p[v]=u;
}
void link(ll u, ll v){
ll pu = get(u), pv = get(v);
if (pu==pv or a[u].out.count(v)) return;
if (a[v].out.count(u)){
unite(pu, pv);
}else if (!a[pu].out.count(pv)){
a[v].in.insert(u);
a[u].out.insert(v);
cnt++;
}
}
void debug(){
for (ll i=1; i<=sz; i++){
cout << i << " -> " << p[i] << ": {comp: ";
for (auto ch:a[i].comp){
cout << ch << " ";
}
cout << "}, {in: ";
for (auto ch:a[i].in){
cout << ch << " ";
}
cout << "}, {out: ";
for (auto ch:a[i].out){
cout << ch << " ";
}
cout << "}\n";
}
}
};
void solve(){
ll n, m; cin >> n >> m;
DSU tree(n);
while (m--){
ll u, v; cin >> u >> v;
tree.link(u, v);
// tree.debug();
cout << tree.cnt << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll t=1;
// cin >> t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
