#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
const int MAXN = 100013;
int N, M;
int dsu[MAXN], siz[MAXN];
vi edge[MAXN];
ll ans;
set<pii> out[MAXN]; //vertices coming out of i.
set<int> in[MAXN]; //vertices coming into clique i.
map<int, int> cl[MAXN]; //edges between cliques
void merge(int u, int v);
int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
void addedge(int u, int v)
{
// cerr << "addedge " << u << ' ' << v << endl;
int x = get(u), y = get(v);
if (x == y || out[x].find({u, y}) != out[x].end())
{
//do nothing.
}
else if (cl[x].find(y) != cl[x].end() || cl[y].find(x) == cl[y].end())
{
// cerr << x << " joins " << y << endl;
cl[x][y]++;
ans += siz[y];
out[x].insert({u, y});
in[y].insert(u);
}
else
{
//added an edge from y to x
merge(x, y);
//fuck, merge.
}
}
void merge(int u, int v)
{
// cerr << "merge " << u << ' ' << v << endl;
//v -> u is connected, connect u -> v now.
cl[v].erase(u);
ans += 2ll * siz[u] * siz[v];
if (SZ(in[v]) + SZ(out[v]) > SZ(in[u]) + SZ(out[u]))
{
swap(u, v);
}
//todo some swap.
for (auto a : out[v])
{
if (a.se != u)
{
out[u].insert(a);
}
else
{
in[u].erase(a.fi);
ans -= siz[u];
}
}
out[v].clear();
ans += siz[v] * (SZ(in[u]));
vpi merges;
for (int w : in[v])
{
//if w -> u exists, just dw about it.
out[get(w)].erase({w, v});
if (in[u].find(w) != in[u].end())
{
//do nothing.
}
//if u -> w exists, this prompts another merge.
else if (cl[u].find(get(w)) != cl[u].end())
{
merges.PB({get(w), u});
}
//if neither, then w -> v.
else
{
ans += siz[u];
in[u].insert(w);
out[get(w)].insert({w, u});
cl[get(w)].erase(v);
cl[get(w)][u]++;
}
}
in[v].clear();
dsu[v] = u;
siz[u] += siz[v];
siz[v] = 0;
sort(ALL(merges));
merges.erase(unique(ALL(merges)), merges.end());
for (pii p : merges)
{
merge(p.fi, p.se);
}
return;
//the how many people have edges into v or edges into u?
}
int32_t main()
{
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> M;
FOR(i, 0, N)
{
dsu[i] = i;
siz[i] = 1;
}
//store edges of the form clique -> node. they are actually reverses of the actual edges.
//also, store clique -> clique edges.
FOR(i, 0, M)
{
int u, v;
cin >> u >> v; u--; v--;
addedge(u, v);
cout << ans << '\n';
//check if u has an edge to anything in v.
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
