// 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]; vector<int> ls[maxn]; ll val[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, int b) {
res -= val[a]; res -= val[b];
val[a] = cal(len(ls[a]), len(adjr[a]));
val[b] = cal(len(ls[b]), len(adjr[b]));
res += val[a]; res += val[b];
}
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 : ls[a]) {
p[v] = b; ls[b].pb(v);
}
ls[a].clear();
for (int v : adj[a]) adj[b].insert(v);
adj[b].erase(a); adj[b].erase(b); adj[a].clear();
for (int v : adjr[a]) adjr[b].insert(v);
adjr[b].erase(a); adjr[b].erase(b); adjr[a].clear();
upd(a, b);
}
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 u, v;
cin >> u >> v; u--; v--;
u = p[u]; v = p[v];
if (u == v) continue;
adj[u].insert(v); adjr[v].insert(u);
if (adjr[u].find(v) != adjr[u].end()) merge(u, v);
else upd(u, v);
cout << res << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
