#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;
const int IN = 0, OUT = 1;
int N, M;
int rep[100001][2], par[100001]; // 0 -> in; 1 -> out
ll sz[100001];
set<int> deg[100001][2];
ll sum = 0;
queue<pii> Q;
int find(int x) {return par[x] = (par[x] == x) ? x : find(par[x]);}
void join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
sum -= sz[a] * sz[a];
sum -= sz[b] * sz[b];
sz[a] += sz[b];
par[b] = a;
sum += sz[a] * sz[a];
int Ain = rep[a][IN], Bin = rep[b][IN];
sum -= deg[Ain][IN].size() * sz[a];
sum -= deg[Bin][IN].size() * sz[b];
if (deg[Ain][IN].size() < deg[Bin][IN].size()) swap(Ain, Bin);
for (const auto &x : deg[Bin][IN]) {
deg[Ain][IN].insert(x);
deg[x][OUT].erase(Bin);
deg[x][OUT].insert(Ain);
}
deg[Bin][IN].clear();
sum += deg[Ain][IN].size() * sz[a];
rep[a][IN] = Ain;
int Aout = rep[a][OUT], Bout = rep[b][OUT];
if (deg[Aout][OUT].size() < deg[Bout][OUT].size()) swap(Aout, Bout);
for (const auto &x : deg[Bout][OUT]) {
deg[Aout][OUT].insert(x);
deg[x][IN].erase(Bout);
deg[x][IN].insert(Aout);
if (deg[rep[find(x)][OUT]][OUT].count(Ain)) Q.push({a, find(x)});
}
deg[Bout][OUT].clear();
rep[a][OUT] = Aout;
//cerr << a << " join " << b << " " << sum << "\n";
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
rep[i][IN] = rep[i][OUT] = i;
par[i] = i;
sz[i] = 1;
}
for (int i = 0; i < M; i++) {
int u, v; cin >> u >> v; u--; v--;
int ruo = rep[find(u)][OUT], rui = rep[find(u)][IN];
int rvo = rep[find(v)][OUT], rvi = rep[find(v)][IN];
if (deg[ruo][OUT].count(rvi) == 0) sum++;
deg[ruo][OUT].insert(rvi);
deg[rvi][IN].insert(ruo);
if (deg[rui][IN].count(rvo)) {
Q.push({find(u), find(v)});
}
while (Q.size()) {
auto [a, b] = Q.front(); Q.pop();
a = find(a), b = find(b);
sum -= 2;
deg[rep[a][IN]][IN].erase(rep[b][OUT]);
deg[rep[b][IN]][IN].erase(rep[a][OUT]);
deg[rep[a][OUT]][OUT].erase(rep[b][IN]);
deg[rep[b][OUT]][OUT].erase(rep[a][IN]);
join(a, b);
}
cout << sum << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
