// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <algorithm>
#include <climits>
#include <ios>
#include<iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ull unsigned ll
#define ln "\n"
#define pll pair<ll, ll>
#define INF 2e18
using namespace std;
struct DSU{
vector<set<ll>> h_in, h_out, lead;
vector<ll> par, sz;
ll n, ecnt;
DSU(ll N){
n=N;
ecnt=0;
par.resize(n+1, -1);
h_in=h_out=lead = vector<set<ll>>(n+1);
for (ll i=1; i<=n; i++) lead[i].insert(i);
sz.resize(n+1, 1);
}
void debug(){
return;
for (ll i=1; i<=n; i++){
cout << i << "::\n";
cout << "lead: ";
for (auto ch:lead[i]) cout << ch << ' ';
cout << "\nin: ";
for (auto ch:h_in[i]) cout << ch << ' ';
cout << "\nout: ";
for (auto ch:h_out[i]) cout << ch << ' ';
cout << ln << ln;
}
}
queue<pair<ll, ll>> unity;
ll get(ll u){
return par[u]==-1?u:par[u]=get(par[u]);
}
void elink(ll u, ll v, int add=1){
ll pu = get(u), pv=get(v);
// cout << "Request: " << u << "->" << v << " - " << pu << " -> " << pv << ln;
if (pu==pv or h_in[pv].count(pu)){
// if (add==0) cout << "Spec: " << u << " " << v << ln;
return;
}else if (h_out[pv].count(pu)){
h_in[pv].insert(pu);
h_out[pu].insert(pv);
unity.push({pu, pv});
}else{
ecnt+=sz[v]*add;
h_in[pv].insert(pu);
h_out[pu].insert(pv);
lead[pv].insert(u);
}
}
void link(ll u, ll v){
elink(u, v);
proc_unities();
debug();
}
void unite(ll u, ll v){
u=get(u); v=get(v);
if (u==v) return;
if (h_in[u].size()+h_out[u].size()+lead[u].size()<h_in[v].size()+h_out[v].size()+lead[v].size()) swap(u, v);
par[v]=u;
// cout << "PDEB: " << ecnt << ":" << sz[u] << ' ' << sz[v] << ln;
ecnt+=sz[u]*lead[v].size()+sz[v]*lead[u].size();
sz[u]+=sz[v];
// cout << "Unite: " << v << "->" << u << ln;
// cout << "PDEB: " << ecnt << ln;
for (auto mem:lead[v]){
ecnt-=sz[u]*lead[u].count(mem);
lead[u].insert(mem);
}
lead[v].clear();
h_in[v].erase(u); h_out[u].erase(v);
h_in[u].erase(v); h_out[v].erase(u);
for (auto mem:h_in[v]){
h_out[mem].erase(v);
elink(mem, u, 0);
}
h_in[v].clear();
for (auto mem:h_out[v]){
h_in[mem].erase(v);
elink(u, mem, 0);
}
h_out[v].clear();
}
void proc_unities(){
while (!unity.empty()){
auto cur = unity.front();
unity.pop();
unite(cur.ff, cur.ss);
}
}
};
void solve(){
ll n, m;
cin >> n >> m;
DSU tr(n);
for (ll i=0; i<m; i++){
ll u, v; cin >> u >> v;
tr.link(u, v);
cout << tr.ecnt << ln;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
ll t=1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
