Submission #551953

#	Time	Username	Problem	Language	Result	Execution time	Memory
551953		i_am_noob	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1113 ms	87904 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

const int mod=1000000007;
const int maxn=100005,maxm=26,maxk=7777714;

//i_am_noob
int n,m,res=0;

int par[maxn];
vector<vector<int>> has(maxn);
unordered_set<int> from[maxn],to[maxn],from2[maxn];

int Find(int x){return x==par[x]?x:par[x]=Find(par[x]);}

void orzck(){
    cin >> n >> m;
    rep(n) par[i]=i,has[i].pb(i);
    rep1(_,m){
        int u,v;
        cin >> u >> v;
        u--,v--;
        if(Find(u)==Find(v)){
            cout << res << "\n";
            continue;
        }
        res-=sz(has[Find(v)])*sz(from2[Find(v)]);
        from[Find(v)].insert(Find(u));
        to[Find(u)].insert(Find(v));
        from2[Find(v)].insert(u);
        res+=sz(has[Find(v)])*sz(from2[Find(v)]);
        u=Find(u),v=Find(v);
        if((!to[u].count(v))||(!to[v].count(u))){
            cout << res << "\n";
            continue;
        }
        queue<int> q;
        while(1){
            res-=sz(has[u])*sz(from2[u]);
            res-=sz(has[v])*sz(from2[v]);
            res-=sz(has[u])*(sz(has[u])-1);
            res-=sz(has[v])*(sz(has[v])-1);
            if(sz(has[u])<sz(has[v])) swap(u,v);
            for(auto i: has[v]) from2[u].erase(i);
            vector<int> tmp;
            for(auto i: from2[v]) if(Find(i)==u) tmp.pb(i);
            for(auto i: tmp) from2[v].erase(i);
            from[u].erase(v),to[u].erase(v);
            from[v].erase(u),to[v].erase(u);
            for(auto i: from[v]) to[i].erase(v),to[i].insert(u);
            for(auto i: to[v]) from[i].erase(v),from[i].insert(u);
            for(auto i: from[v]){
                if(to[u].count(i)) q.push(i);
                else from[u].insert(i);
            }
            for(auto i: to[v]){
                if(from[u].count(i)) q.push(i);
                else to[u].insert(i);
            }
            for(auto i: has[v]) has[u].pb(i);
            for(auto i: from2[v]) from2[u].insert(i);
            par[v]=u;
            res+=sz(has[u])*sz(from2[u]);
            res+=sz(has[u])*(sz(has[u])-1);
            v=-1;
            while(1){
                if(q.empty()) break;
                v=q.front();
                q.pop();
                if(v==par[v]) break;
                else v=-1;
            }
            if(v==-1) break;
        }
        cout << res << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    orzck();
    return 0;
}

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