Submission #359662

#	Time	Username	Problem	Language	Result	Execution time	Memory
359662		Nima_Naderi	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1438 ms	129644 KiB

joitter2

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 4e5 + 10;
ll n, m, ans, pnt;
ll Par[MXN], Sz[MXN];
set<ll> In[MXN], Out[MXN], To[MXN], Comp[MXN];
vector<pair<ll, ll>> Q;
ll Find(ll x){
    return (x == Par[x] ? x : Par[x] = Find(Par[x]));
}
void add(ll u, ll v){
    if(u == v) return;
    Out[u].insert(v), In[v].insert(u);
    if(In[u].find(v) != In[u].end()) Q.push_back({u, v});
}
void Union(ll x, ll y){
    x = Find(x), y = Find(y);
    if(x == y) return;
    if(Sz[x] < Sz[y]) swap(x, y);
    /*
    cout << "====================\n";
    cout << x << ' ' << y << '\n';
    cout << ans << '\n';
    cout << To[x].size() << '\n';
    cout << To[y].size() << '\n';
    cout << "====================\n";
    //*/
    ans -= Sz[x] * (Sz[x] - 1);
    ans -= Sz[y] * (Sz[y] - 1);

    ans -= 1ll * To[x].size() * (Sz[x]);
    ans -= 1ll * To[y].size() * (Sz[y]);

    for(auto X : In[y])  Out[X].erase(y);
    for(auto X : Out[y]) In[X].erase(y);
    for(auto X : In[y])  add(X, x);
    for(auto X : Out[y]) add(x, X);

    for(auto X : Comp[y]){
        auto itr = To[x].find(X);
        if(itr == To[x].end()) continue;
        To[x].erase(itr);
    }
    for(auto X : To[y]){
        if(Find(X) != x){
            To[x].insert(X);
        }
    }
    In[y].clear(), Out[y].clear(), To[y].clear();
    Sz[x] += Sz[y], Par[y] = x;
   // cout << "* " << Sz[x] * (Sz[x] - 1) + 1ll * To[x].size() * (Sz[x]) << '\n';
    ans += 1ll * To[x].size() * (Sz[x]);
    ans += Sz[x] * (Sz[x] - 1);
    for(auto X : Comp[y]) Comp[x].insert(X);
    Comp[y].clear();
    /*
    cout << "=====================\n";
    cout << x << '\n';
    cout << "COMP : \n";
    for(auto X : Comp[x]) cout << X << ' '; cout << '\n';
    cout << "In : \n";
    for(auto X : In[x]) cout << X << ' '; cout << '\n';
    cout << "Out : \n";
    for(auto X : Out[x]) cout << X << ' '; cout << '\n';
    cout << "To : \n";
    for(auto X : To[x]) cout << X << ' '; cout << '\n';
    cout << "=====================\n";
    //*/
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) Par[i] = i, Sz[i] = 1, Comp[i].insert(i);
    for(int i = 1; i <= m; i ++){
        ll u, v; cin >> u >> v;
        if(Find(u) == Find(v) || To[Find(v)].find(u) != To[Find(v)].end()){
            cout << ans << '\n';
            continue;
        }
        To[Find(v)].insert(u), ans += Sz[Find(v)];
        add(Find(u), Find(v));
        while(pnt < Q.size()){
            ll x, y; tie(x, y) = Q[pnt];
            pnt ++;
            Union(x, y);
        }
        cout << ans << '\n';
    }
    //cout << To[5].size() << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:86:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         while(pnt < Q.size()){
      |               ~~~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83