#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, ans = 0, p[N], sz[N];
multiset<int> out[N];
set<pair<int,int>> in[N];
void _(int x, int y) {
if(out[x].find(y) != out[x].end()) out[x].erase(y);
while(in[y].upper_bound({x, 0}) != in[y].end() && (*in[y].upper_bound({x, 0})).f == x) {
pii p = *in[y].upper_bound({x, 0});
in[y].erase(p);
ans -= sz[y];
}
}
int find(int x) {
return (p[x] == x ? p[x] : p[x] = find(p[x]));
}
void merge(int u, int v) {
int U = find(u), V = find(v);
if(U == V) return;
_(U, V);
_(V, U);
if((int)in[U].size() + (int)out[U].size() < (int)in[V].size() + (int)out[V].size()) swap(U, V);
p[V] = U;
ans += sz[U] * sz[V] * 2;
sz[U] += sz[V];
ans += (int)in[U].size() * sz[V];
vector<int> nbx;
while(out[V].size()) {
int x = *out[V].begin();
out[V].erase(out[V].find(x));
out[U].insert(x);
pii p = *in[x].upper_bound({V, 0});
in[x].erase(p); p.f = U; in[x].insert(p);
if(out[x].find(U) != out[x].end()) nbx.push_back(x);
}
while(in[V].size()) {
pii p = *in[V].begin();
int x = p.f;
out[x].erase(out[x].find(V));
in[V].erase(p); in[U].insert(p);
if(in[U].find(p) == in[U].end()) ans += (sz[U] - sz[V]), out[x].insert(U);
else ans -= sz[V];
if(out[U].find(x) != out[U].end()) nbx.push_back(x);
}
for(int i = 0; i < nbx.size(); i++) merge(U, nbx[i]);
}
main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
int U = find(u), V = find(v);
if(out[V].find(U) != out[V].end()) merge(u, v);
else
if(in[V].find({U, u}) == in[V].end()) ans += sz[V], out[U].insert(V), in[V].insert({U, u});
cout << ans << endl;
}
}
Compilation message
joitter2.cpp: In function 'void merge(long long int, long long int)':
joitter2.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0; i < nbx.size(); i++) merge(U, nbx[i]);
| ~~^~~~~~~~~~~~
joitter2.cpp: At global scope:
joitter2.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
53 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
