| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1182660 | vako_p | Making Friends on Joitter is Fun (JOI20_joitter2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " ---> " << x << endl;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int mxN = 1e6 + 5;
ll n,m;
struct ds{
vector<ll> node,sz,par,node1;
vector<set<pair<ll,ll>>> in,out;
ll ans = 0;
void init(){
par.resize(n + 5);
sz.assign(n + 5, 1LL);
node.resize(n + 5);
node1.resize(n + 5);
in.resize(n + 5);
out.resize(n + 5);
for(int i = 0; i < n + 5; i++) par[i] = node[i] = node1[i] = i;
}
ll find(ll at){
if(at == par[at]) return at;
par[at] = find(par[at]);
return par[at];
}
void merge(ll p1, ll p2){
pair<ll,ll> a = {find(p1), node[find(p1)]}, b = {find(p2), node[find(p2)]};
if(a == b) return;
if(in[a.ff].size() + out[a.sd].size() < in[b.ff].size() + out[b.sd].size()) swap(a, b);
// cout << a.ff << ' ' << b.sd << "--------> " << (*in[a.ff].begin()).ff << '\n';
for(auto it = in[a.ff].lower_bound({b.sd, 0}); it != in[a.ff].end() and (*it).ff == b.sd; it = in[a.ff].lower_bound({b.sd, 0})){
ans -= sz[b.ff];
in[a.ff].erase(it);
}
for(auto it = in[b.ff].lower_bound({a.sd, 0}); it != in[b.ff].end() and (*it).ff == a.sd; it = in[b.ff].lower_bound({a.sd, 0})){
ans -= sz[a.ff];
in[b.ff].erase(it);
}
ans += sz[a.ff] * sz[b.ff] * 2;
par[b.ff] = a.ff;
ll sz1 = sz[a.ff],sz2 = sz[b.ff];
sz[a.ff] += sz[b.ff];
vector<ll> v;
// cout << a.ff << ' ' << b.ff << ' ' << in[a.ff].size() << '\n';
for(auto it : in[b.ff]){
in[a.ff].insert(it);
out[it.ff].erase({b.ff, it.sd});
out[it.ff].insert({a.ff, it.sd});
ll at = node1[it.ff];
// debug(it.ff);
// debug(at);
auto it1 = in[at].lower_bound({a.ff, 0LL});
if(it1 != in[at].end() and (*it1).ff == a.ff) v.pb(at);
}
in[b.ff].clear();
// if(out[a.sd].size() < out[b.sd].size()){
// node[a.ff] = b.sd;
// node1[b.sd] = a.ff;
// swap(sz1, sz2);
// swap(a, b);
// }
for(auto it = out[a.sd].lower_bound({b.ff, 0}); it != out[a.sd].end() and (*it).ff == b.ff; it = out[a.sd].lower_bound({b.ff, 0})){
out[a.sd].erase(it);
}
for(auto it = out[b.sd].lower_bound({a.ff, 0}); it != out[b.sd].end() and (*it).ff == a.ff; it = out[b.sd].lower_bound({a.ff, 0})){
out[b.sd].erase(it);
}
ans += out[a.sd].size() * sz2 + out[b.sd].size() * sz1;
for(auto it : out[b.sd]){
out[a.sd].insert(it);
in[it.ff].erase({b.sd, it.sd});
in[it.ff].insert({a.sd, it.sd});
ll at = node[it.ff];
auto it1 = in[a.ff].lower_bound({at, 0LL});
if(it1 != in[a.ff].end() and (*it1).ff == at) v.pb(it.ff);
}
out[b.sd].clear();
ll p = find(a.ff);
// debug(v.size());
for(auto it : v) merge(it, p);
}
void set(ll a, ll b){
ll p = find(a),p1 = find(b);
// cout << a << ' ' << b << "----> " << node[p1] << '\n';
if(p == p1 or out[node[p1]].find({p, a}) != out[node[p1]].end()) return;
ans += sz[p1];
in[p].insert({node[p1], a});
out[node[p1]].insert({p, a});
auto it = in[p1].lower_bound({p, 0});
if(it != in[p1].end() and (*it).ff == p) merge(p, p1);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
ds s;
s.init();
for(int i = 0; i < m; i++){
ll a,b;
cin >> a >> b;
s.set(a, b);
cout << s.ans << '\n';
}
}