/*input
6 10
1 2
2 3
3 4
4 5
5 6
6 5
5 4
4 3
3 2
2 1
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <ctime>
using namespace std;
const int MAXN = 100007;
int N, M;
int root[MAXN];
int64_t E = 0, cnt[MAXN], deg_in[MAXN], deg_out[MAXN];
unordered_map<int, unordered_set<int>> edges[MAXN];
unordered_set<int> back_edges[MAXN];
stack<pair<int, int>> join_stack;
void init()
{
for (int u = 1; u <= N; ++u) cnt[u] = 1, root[u] = u;
}
int get_root(int u) { return (root[u] == u ? u : root[u] = get_root(root[u])); }
void delete_edge(int u, int v)
{
auto it = edges[u].find(v);
assert(it != edges[u].end());
int64_t cur = it->second.size() * cnt[v];
deg_out[u] -= it->second.size(), deg_in[v] -= it->second.size(), E -= cur;
edges[u].erase(it);
back_edges[v].erase(u);
}
void add_edge(int u, int v, unordered_set<int> sources)
{
back_edges[v].insert(u);
for (int x : sources) {
if (edges[u][v].find(x) == edges[u][v].end()) {
++deg_out[u], ++deg_in[v], E += cnt[v];
edges[u][v].insert(x);
}
}
}
void join(int u, int v)
{
u = get_root(u), v = get_root(v);
if (u == v) return;
if (deg_in[u] + deg_out[u] < deg_in[v] + deg_out[v]) swap(u, v);
// cout << u << ' ' << v << endl;
// between u and v
if (edges[u].find(v) != edges[u].end()) delete_edge(u, v);
if (edges[v].find(u) != edges[v].end()) delete_edge(v, u);
E += cnt[u] * cnt[v] * 2;
// cout << "X " << E << endl;
auto edges_v = edges[v];
for (auto batch : edges_v) {
int w = batch.first;
if (back_edges[u].find(w) != back_edges[u].end()) join_stack.emplace(u, w);
else {
delete_edge(v, w);
add_edge(u, w, batch.second);
}
}
auto back_edges_v = back_edges[v];
for (int w : back_edges_v) {
if (back_edges[w].find(u) != back_edges[w].end()) join_stack.emplace(u, w);
else {
auto sources = edges[w][v];
delete_edge(w, v);
add_edge(w, u, sources);
}
}
E += cnt[v] * deg_in[u];
cnt[u] += cnt[v];
root[v] = u;
}
void query(int u, int v)
{
unordered_set<int> sources = {u};
int root_u = get_root(u), root_v = get_root(v);
add_edge(root_u, root_v, sources);
// cout << "Y " << E << endl;
if (back_edges[root_u].find(root_v) != back_edges[root_u].end()) {
join_stack.emplace(root_u, root_v);
}
while (!join_stack.empty()) {
auto p = join_stack.top();
join_stack.pop();
join(p.first, p.second);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
init();
while (M--) {
int u, v;
cin >> u >> v;
query(u, v);
cout << E << '\n';
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
