#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define dbg(x) cerr << "[" << #x << "] = [" << x << "]\n"
template<class T> ostream& operator<< (ostream& out, vector<T> v) {
out << '[';
for (int i = 0; i < v.size(); ++i) {
if (i > 0) {
out << ", ";
}
out << v[i];
}
return out << ']';
}
template<class T> ostream& operator<< (ostream& out, set<T> v) {
return out << vector<T>(v.begin(), v.end());
}
template<class A, size_t sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
out << '[';
for (int i = 0; i < sz; ++i) {
if (i > 0) out << ", ";
out << a[i];
}
return out << ']';
}
template<class A, class B> ostream& operator<< (ostream& out, pair<A, B> p) {
return out << '[' << p.first << ", " << p.second << ']';
}
template<class A, class B> ostream& operator<< (ostream& out, map<A, B> mp) {
return out << vector<pair<A, B>>(mp.begin(), mp.end());
}
const int mxN=1e5;
int n, m, p[mxN];
set<int> adj[mxN][2], to[mxN], back[mxN]; // forward and backward edges to other components, from i->component, component->i
vector<int> cmp[mxN];
queue<ar<int, 2>> q;
ll ans;
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
ll calc(int i) {
assert(i==p[i]);
ll x=cmp[i].size();
return x*(x-1)+(ll)back[i].size()*x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; ++i) {
p[i]=i;
cmp[i]={i};
}
while(m--) {
int u, v;
cin >> u >> v, --u, --v;
if (find(u)==find(v))
continue;
if (to[u].find(find(v))==to[u].end()) {
ans+=cmp[find(v)].size();
to[u].insert(find(v));
back[find(v)].insert(u);
}
u=find(u), v=find(v);
if (adj[u][0].find(v)==adj[u][0].end()) {
adj[u][0].insert(v);
adj[v][1].insert(u);
if (adj[u][1].find(v)!=adj[u][1].end())
q.push({u, v});
}
for (; q.size(); q.pop()) {
u=find(q.front()[0]), v=find(q.front()[1]);
//cout << "trying to merge " << u << " " << v << endl;
//dbg(to[u]), dbg(to[v]), dbg(back[u]), dbg(back[v]);
if (u==v)
continue;
if (cmp[u].size()<cmp[v].size())
swap(u, v);
ans-=calc(u)+calc(v);
for (int j : {0, 1}) {
for (int rep=0; rep<2; ++rep) {
auto it=adj[u][j].find(v);
assert(it!=adj[u][j].end());
adj[u][j].erase(it);
swap(u, v);
}
}
for (int i : cmp[v]) {
if (to[i].find(u)!=to[i].end()) {
to[i].erase(u);
back[u].erase(i);
}
cmp[u].push_back(i);
}
vector<int>().swap(cmp[v]);
for (int i : back[v]) {
auto it=to[i].find(v);
assert(it!=to[i].end());
to[i].erase(it);
if (find(i)!=u) {
to[i].insert(u);
back[u].insert(i);
}
}
set<int>().swap(back[v]);
//back[u].erase(v);
//cout << adj[v][0].size() << " " << adj[v][1].size() << " " << adj[0][0].size() << endl;
for (int j : {0, 1}) {
for (int i : adj[v][j]) {
//cout << j << " " << v << " " << i << endl;
adj[u][j].insert(i);
auto it=adj[i][j^1].find(v);
assert(it!=adj[i][j^1].end());
adj[i][j^1].erase(it);
adj[i][j^1].insert(u);
if (adj[u][j^1].find(i)!=adj[u][j^1].end())
q.push({u, i});
}
set<int>().swap(adj[v][j]);
}
//dbg(to[u]), dbg(to[v]), dbg(back[u]), dbg(back[v]);
ans+=calc(u);
p[v]=u;
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
