# Untitled

a guest
Jun 9th, 2021
657
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. #define all(x) (x).begin(), (x).end()
4. #define itn int
5. #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end())
6.
7. using namespace std;
8.
9. inline int nxt() {
10.     int x;
11.     scanf("%d", &x);
12.     return x;
13. }
14.
15. struct Edge {
16.     int from, to;
17.     int index;
18.
19.     bool operator <(const Edge& ot) const {
20.         return index < ot.index;
21.     }
22. };
23.
24. struct Vertex {
25.     int w;
26.     vector<int> to; // edge indices
27. };
28.
29. struct Graph {
30.     vector<Vertex> vertices;
31.     vector<Edge> edges;
33.     int low, high;
34.
35.     vector<int> color;
36.     vector<char> used;
37.     vector<int> index;
39.     vector<int> st;
40.     int cur_time;
41.     vector<int> comp_sizes;
42.
43.     void dfs(int v, int threshold);
44.
45.     void solve();
46. };
47.
48. ostream& operator <<(ostream& ostr, const Graph& g) {
49.     ostr << "G{" << g.vertices.size() << " vertices, " << g.edges.size() << " edges:";
50.     for (auto e : g.edges) {
51.         ostr << " (" << e.from + 1 << " -> " << e.to + 1 << " [" << e.index << "])";
52.     }
53.     ostr << "}";
54.     return ostr;
55. }
56.
57. void Graph::dfs(int v, int threshold) {
58.     index[v] = lowlink[v] = cur_time++;
59.     used[v] = 1;
60.     st.push_back(v);
61.     for (int e_id : vertices[v].to) {
62.         if (edges[e_id].index >= threshold) {
63.             continue;
64.         }
65.         int to = edges[e_id].to;
66.         if (index[to] == -1) {
67.             dfs(to, threshold);
69.         } else if (used[to]) {
71.         }
72.     }
73.
74.     if (lowlink[v] == index[v]) {
75.         int clr = comp_sizes.size();
76.         comp_sizes.push_back(0);
77.         while (true) {
78.             int w = st.back();
79.             st.pop_back();
80.             color[w] = clr;
81.             comp_sizes.back() += vertices[w].w;
82.             used[w] = 0;
83.             if (w == v) {
84.                 break;
85.             }
86.         }
87.     }
88. }
89.
90. #define cerr if (0) cerr
91.
92. void Graph::solve() {
93.     if (low >= high) {
94.         return;
95.     }
96.     if (edges.empty()) {
97.         return;
98.     }
99.
100.     int idx = (low + high + 1) / 2;
101. /*  if ((*answer)[idx] == 0) {
103.         cerr << "answer[" << idx << "] = answer[" << low << "]\n";
104.     }
105. */
106.     cerr << "[" << low << ", " << high << "]: " << (*this) << "\n";
107.
108.     color.assign(vertices.size(), 0);
109.     used.assign(vertices.size(), 0);
110.     index.assign(vertices.size(), -1);
112.     st = {};
113.     cur_time = 0;
114.     comp_sizes = {};
115.
116.     for (int v = 0; v < (int)vertices.size(); ++v) {
117.         if (index[v] == -1) {
118.             dfs(v, idx);
119.         }
120.     }
121.
122.     cerr << "colors:";
123.     for (int i = 0; i < (int)vertices.size(); ++i) {
124.         cerr << " " << color[i];
125.     }
126.     cerr << "\n";
127.
128.     long long tmp = 0;
129.     for (auto s : comp_sizes) {
130.         tmp += 1ll * s * (s - 1) / 2;
131.     }
132.     for (auto v : vertices) {
133.         tmp -= 1ll * v.w * (v.w - 1) / 2;
134.     }
135.
137.     (*answer)[high + 1] -= tmp;
138.     cerr << "answer[" << idx << "] += " << tmp << "\n\n";
139.
140.     vector<Graph> left(comp_sizes.size());
141.     Graph right;
142.
143.     vector<int> in_graph_index(vertices.size());
144.     vector<int> total_w(vertices.size());
145.     for (int i = 0; i < (int)vertices.size(); ++i) {
146.         in_graph_index[i] = left[color[i]].vertices.size();
147.         left[color[i]].vertices.push_back({vertices[i].w, {}});
148.     }
149.     for (int i = 0; i < (int)comp_sizes.size(); ++i) {
150.         right.vertices.push_back({comp_sizes[i], {}});
151.     }
152.     for (auto e : edges) {
153.         if (color[e.from] == color[e.to]) {
154.             if (e.index < idx) {
155.                 left[color[e.from]].vertices[in_graph_index[e.from]].to.push_back(left[color[e.from]].edges.size());
156.                 left[color[e.from]].edges.push_back({in_graph_index[e.from], in_graph_index[e.to], e.index});
157.             }
158.         } else {
159.             right.vertices[color[e.from]].to.push_back(right.edges.size());
160.             right.edges.push_back({color[e.from], color[e.to], e.index});
161.         }
162.     }
163.     for (auto& g : left) {
164.         g.low = low;
165.         g.high = idx - 1;
167.     }
168.     right.low = idx;
169.     right.high = high;
171.
172.     for (auto g : left) {
173.         g.solve();
174.     }
175.     right.solve();
176. }
177.
178. int main() {
179.     int n = nxt(), m = nxt();
180.     vector<long long> answer(m + 2);
181.     Graph g;
182.     for (int i = 0; i < n; ++i) {
183.         g.vertices.push_back({1, {}});
184.     }
185.     for (int i = 0; i < m; ++i) {
186.         int u = nxt() - 1, v = nxt() - 1;
187.         g.vertices[u].to.push_back(i);
188.         g.edges.push_back({u, v, i});
189.     }
191.     g.low = 0;
192.     g.high = m;
193.     g.solve();
196.     for (int i = 1; i < (int)answer.size(); ++i) {