#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 3e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;
struct Edge {
int u, v, prio;
bool operator < (const Edge &other) const {
return prio > other.prio || (prio == other.prio && u < other.u) || (prio == other.prio && u == other.u && v < other.v);
}
};
int n, m;
vector<int> cc;
map<pii, int> dEc;
set<Edge> pq;
set<pii> inS[N];///fs: cpn cua no
ll res = 0;
void Insert (pii cur) {
pii cur2 = cur;
if (cur2.fs > cur2.se) swap(cur2.fs, cur2.se);
if (pq.find({cur2.fs, cur2.se, 1}) != pq.end()) {
pq.erase(pq.find({cur2.fs, cur2.se, 1}));
}
pq.insert({cur2.fs, cur2.se, dEc[cur2] + dEc[MP(cur2.se, cur2.fs)]});
}
void Erase (pii cur) {
pii cur2 = cur;
if (cur2.fs > cur2.se) swap(cur2.fs, cur2.se);
pq.erase(pq.find({cur2.fs, cur2.se, 1}));
}
struct Disjoin_set {
ll lab[N], sz[N];
void init (int n) {
rep (i, 1, n) {
lab[i] = i, sz[i] = 1;
}
}
int Find (int u) {
return u == lab[u] ? u : Find(lab[u]);
}
void Join (int u, int v) {
int uu = Find(u), vv = Find(v);
if (uu == vv) return ;
if (inS[vv].find(MP(uu, u)) == inS[vv].end()) res += sz[vv];
dEc[{uu, vv}] = 1;
inS[vv].insert({uu, u});
Insert(MP(uu, vv));
return ;
}
void noi (int u, int v) {
pq.erase(pq.find({u, v, 2}));
// cout << u <<" "<<v<<": \n";
// iter (&id, pq) {
// cout << id.u<<","<<id.v<<","<<id.prio <<" ";
// }
// cout<<"\n";
if (SZ(inS[u]) < SZ(inS[v])) swap(u, v);
///delete old edge
res -= sz[u] * (sz[u] - 1) + sz[v] * (sz[v] - 1);
///delete cross-edge
auto it = inS[u].lower_bound({v, 0});
while (1) {
if (it == inS[u].end() || it->fs != v) break;
res -= sz[v];
it = inS[u].erase(it);
}
it = inS[v].lower_bound({u, 0});
while (1) {
if (it == inS[v].end() || it->fs != u) break;
res -= sz[u];
it = inS[v].erase(it);
}
///add all edge
res += (sz[u] + sz[v]) * (sz[u] + sz[v] - 1);
///add weak edge
res += SZ(inS[v]) * sz[u] + SZ(inS[u]) * sz[v];
///remove incident
iter (&id, inS[v]) {
if (inS[u].find(id) != inS[u].end()) res -= sz[v] + sz[u];
}
///updating pq
iter (&id, inS[v]) {
dEc[{id.fs, u}] = 1;
inS[u].insert(id);
Erase(MP(id.fs, v));
Insert(MP(id.fs, u));
}
set<pii> ().swap(inS[v]);
lab[v] = u;
sz[u] += sz[v];
}
void simulate () {
while (!pq.empty()) {
if (pq.begin()->prio == 1) break;
else noi(pq.begin()->u, pq.begin()->v);
}
}
}DSU;
void solution () {
cin >> n >> m;
DSU.init(n);
rep (i, 1, m) {
int u, v;
cin >> u >> v;
DSU.Join(u, v);
DSU.simulate();
cout << res <<"\n";
}
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7
return->break
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
