#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<int> in[MAXN]; //vertices into the CLIQUE i.
map<int, set<int> > out[MAXN]; //edges between cliques. out[x][y] stores for all x -> y,what are the actual vertices?
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 || in[y].find(u) != in[y].end())
{
//do nothing.
}
else if (SZ(out[x][y]) > 0 || SZ(out[y][x]) == 0)
{
//maybe x -> y has an edge already?
out[x][y].insert(u);
ans += siz[y];
in[y].insert(u);
}
else
{
for (auto a : out[y][x])
{
in[x].erase(y);
ans -= siz[x];
}
// cerr << "ans = " << ans << endl;
out[y].erase(x);
//y -> x has an edge already.
merge(x, y);
}
}
void merge(int u, int v)
{
if (get(u) == get(v)) return;
// cerr << "merge " << u << ' ' << v << endl;
//GUARANTEE THAT ALL EDGES U -> V ARE COMPLETELY CLEARED.
ans += 2ll * siz[u] * siz[v];
// cerr << "ans = " << ans << endl;
//now the actual merging part.
//x -> both: do nothing
//x -> one: connect it to the other.
//x -> u and v -> x: MERGE AGAIN.
set<int> merges;
//this takes care of all edges stemming out of the connected component of v.
for (auto it = out[v].begin(); it != out[v].end();)
{
if ((it -> se).empty())
{
it = out[v].erase(it);
continue;
}
int cc = it -> fi;
// cerr << v << " -> " << cc << endl;
if (SZ(out[cc][u]) > 0)
{
//merge.
for (auto a : it -> se)
{
in[cc].erase(a);
ans -= siz[cc];
}
for (auto a : out[cc][u])
{
in[u].erase(a);
ans -= siz[u];
}
out[cc].erase(u);
it = out[v].erase(it);
merges.insert(cc);
}
else
{
for (auto a : it -> se)
{
out[v][it -> fi].insert(a);
}
it++;
}
}
int cnt = 0, cnt1 = 0;
for (int w : in[v])
{
// cerr << "w = " << w << endl;
int cc = get(w);
out[cc][v].erase(w);
if (merges.find(cc) != merges.end() || SZ(out[u][cc]) > 0)
{
// cerr << "pity " << w << endl;
for (int z : out[u][cc])
{
ans -= siz[cc];
in[cc].erase(z);
}
// cerr << "ans " << ans << endl;
out[u].erase(cc);
merges.insert(cc);
ans -= siz[v];
// cerr << "ans " << ans << endl;
continue;
}
else if (in[u].find(w) != in[u].end())
{
cnt++;
}
else
{
in[u].insert(w);
out[cc][u].insert(w);
ans += siz[u];
cnt1++;
}
}
// cerr << SZ(in[u]) << ' ' << cnt << ' ' << cnt1 << endl;
ans += (SZ(in[u]) - cnt - cnt1) * siz[v];
in[v].clear();
dsu[v] = u;
siz[u] += siz[v];
siz[v] = 0;
// cerr << "ans = " << ans << endl;
// FOR(i, 0, N)
// {
// cerr << "in " << i << ":";
// for (int x : in[i])
// {
// cerr << ' ' << x;
// }
// cerr << endl;
// }
for (auto a : merges)
{
merge(u, a);
}
return;
}
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;
}
Compilation message
joitter2.cpp: In function 'void addedge(int, int)':
joitter2.cpp:70:19: warning: unused variable 'a' [-Wunused-variable]
for (auto a : out[y][x])
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
