// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
int n, q;
const int maxn = 4e5 + 4;
int p[maxn]; ll val[maxn];
vector<int> ls[maxn]; set<int> A[maxn];
set<int> adj[maxn], adjr[maxn]; ll res = 0;
ll cal(ll sz, ll t) {
return (sz * t) + sz * (sz - 1);
}
void upd(int a) {
res -= val[a];
val[a] = cal(len(ls[a]), len(A[a]));
res += val[a];
}
void merge(int a, int b) {
a = p[a]; b = p[b];
if (a == b) return ;
if (len(ls[a]) > len(ls[b])) swap(a, b);
for (int v : A[a]) {
if (p[v] == a || p[v] == b) continue;
A[b].insert(v);
}
A[a].clear();
for (int v : ls[a]) {
p[v] = b; ls[b].pb(v);
A[b].erase(v);
}
ls[a].clear();
vector<int> vc;
for (int v : adj[a]) {
if (v == a || v == b) continue;
adj[b].insert(v);
adjr[v].erase(a); adjr[v].insert(b);
if (adjr[b].find(v) != adjr[b].end()) vc.pb(v);
}
adj[b].erase(a); adj[a].clear();
for (int v : adjr[a]) {
if (v == a || v == b) continue;
adjr[b].insert(v);
adj[v].erase(a); adj[v].insert(b);
if (adj[b].find(v) != adj[b].end()) vc.pb(v);
}
adjr[b].erase(a); adjr[a].clear();
upd(a), upd(b);
for (int v : vc) merge(b, v);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 0; i < n; i++) {
p[i] = i; ls[i].pb(i);
}
for (int i = 0; i < q; i++) {
int u1, v1;
cin >> u1 >> v1; u1--; v1--;
int u = p[u1], v = p[v1];
if (u == v) continue;
A[v].insert(u1);
adj[u].insert(v); adjr[v].insert(u);
if (adjr[u].find(v) != adjr[u].end()) merge(u, v);
else upd(u), upd(v);
cout << res << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
68440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
68440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
68440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
