This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 1e5 + 5;
typedef pair<int,int> ii;
int p[N];
int s[N];
ll ans = 0;
queue<ii> pending;
int lead(int x) {
return p[x] == x ? x : p[x] = lead(p[x]);
}
struct Edge {
int pa, a;
int pb;
Edge(int _a = 0,int _b = 0) : pa(lead(_a)), a(_a), pb(lead(_b)) {}
};
bool operator < (const Edge&x,const Edge&y) {
auto tmp1 = make_tuple(x.pa,x.pb,x.a);
auto tmp2 = make_tuple(y.pa,y.pb,y.a);
return tmp1 < tmp2;
}
set<Edge> fr[N];
set<Edge> to[N];
bool Try(int x,int y) { //an egde directed from x to y
int a = lead(x);
int b = lead(y);
Edge E(y,x); E.a = 0;
auto it = fr[b].lower_bound(E);
bool ok = 0;
while (it != fr[b].end()) {
if ((*it).pa != b) break;
if ((*it).pb != a) break;
fr[b].erase(*it);
to[a].erase(*it); ans -= s[a];
ok = 1;
it++;
}
if (ok) {
pending.push(ii(a,b));
return 0;
}
if(!fr[a].count(Edge(x,y))) {
fr[a].insert(Edge(x,y));
to[b].insert(Edge(x,y)); ans += s[b];
}
return 1;
}
bool join(int x,int y) {
x = lead(x);
y = lead(y);
if (x == y) return 0;
if (to[x].size() < to[y].size())
swap(x,y);
ans -= 1ll * s[x] * (s[x] - 1);
ans -= 1ll * s[y] * (s[y] - 1);
ans += 1ll * s[y] * sz(to[x]);
ans -= 1ll * s[y] * sz(to[y]);
p[y] = x;
s[x] += s[y];
for(Edge E : to[y]) fr[E.pa].erase(E), Try(E.a,x);
for(Edge E : fr[y]) to[E.pb].erase(E), Try(E.a,E.pb),
ans -= s[E.pb];
fr[y].clear();
to[y].clear();
ans += 1ll * s[x] * (s[x] - 1);
return 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int m; cin >> m;
iota(p + 1,p + 1 + n,1);
fill(s + 1,s + 1 + n,1);
for(int i = 0 ; i < m ; ++i) {
int x; cin >> x;
int y; cin >> y;
int a = lead(x);
int b = lead(y);
if (a != b)
Try(x,y);
while (pending.size()) {
int x = pending.front().X;
int y = pending.front().Y;
pending.pop();
join(x,y);
}
// if (i == 2) {
// for(int j = 1 ; j <= n ; ++j) if (j == p[j]) {
// cerr << "Info of " << j << "-th component:\n";
// for(Edge e : fr[j]) cerr << e.a << "-" << e.b << "\n";
// for(Edge e : to[j]) cerr << e.a << "-" << e.b << "\n";
// }
// }
ll ans = 0;
for(int j = 1 ; j <= n ; ++j)
if (j == p[j])
ans += 1ll * s[j] * (s[j] - 1),
ans += 1ll * s[j] * sz(to[j]);
cout << ans << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |