# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1177019 | arwakhattab | Making Friends on Joitter is Fun (JOI20_joitter2) | C++20 | 21 ms | 45568 KiB |
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';
const int N = 1e5;
struct DSU {
int n;
vector<int> par, size;
vector<bitset<N> > msk;
DSU() {
}
DSU(int n) : n(n) {
par.assign(n, 0);
size.assign(n, 1);
msk.assign(n, 0);
for (int i = 0; i < n; i++) {
par[i] = i;
msk[i][i] = true;
}
}
int find(int v) {
return (v == par[v] ? v : par[v] = find(par[v]));
}
void set(int u, int v) {
msk[find(v)][u] = true;
}
bool get(int u, int v) {
return msk[find(v)][u];
}
ll get_ans(int u) {
u = find(u);
ll m = size[u];
return m * (msk[u].count() - 1);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (size[a] < size[b]) swap(a, b);
par[b] = a;
size[a] += size[b];
msk[a] |= msk[b];
return true;
}
int sz(int v) {
return size[find(v)];
}
};
void solve() {
int n, m;
cin >> n >> m;
set<pair<int, int> > edges;
DSU dsu(n);
ll ans = 0;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u, --v;
if (edges.contains({v, u})) {
ans -= dsu.get_ans(u);
ans -= dsu.get_ans(v);
dsu.unite(u, v);
ans += dsu.get_ans(u);
} else if (!dsu.get(u, v)) {
dsu.set(u, v);
ans += dsu.sz(v);
}
edges.insert({u, v});
cout << ans << nl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("../in.txt", "r", stdin);
freopen("../out.txt", "w", stdout);
#endif
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |