Submission #1225568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225568		Gray	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	364 ms	50140 KiB

joitter2

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
const ll INF = 2e18;
const ll MOD = 1e9+7;
using namespace std;

struct DSU{
    vector<ll> p;
    vector<set<ll>> nodes;
    vector<set<ll>> in, outp;
    queue<pair<ll, ll>> buffer;
    ll n, cnt;
    DSU(ll N){
        n=N; p.resize(N+1, -1); cnt=0;
        nodes.resize(n+1); for (ll i=1; i<=n; i++) nodes[i].insert(i);
        in.resize(n+1); outp.resize(n+1);
    }
    ll get(ll x){
        return p[x]==-1?x:p[x]=get(p[x]);
    }
    void unite(ll u, ll v){
        if (in[u].size()+nodes[u].size()<in[v].size()+nodes[v].size()) swap(u, v);
        p[v]=u; vector<ll> ers;
        // cout << u << " & " << v << ln;
        // cout << nodes[u].size() << " and " << nodes[v].size() << ln;
        // cout << "From: " << cnt << ln;
        for (auto cv:in[v]){
            if(get(cv)==u){
                cnt-=nodes[v].size();
                ers.push_back(cv);
            }
        }
        for (auto cv:ers){
            in[v].erase(cv);
        }
        for (auto cv:nodes[v]){
            if (in[u].count(cv)){
                cnt-=nodes[u].size();
            }
            in[u].erase(cv);
        }
        outp[u].erase(v); outp[v].erase(u);
        // cout << "Mid: " << cnt << ln;
        cnt+=in[u].size()*nodes[v].size()+in[v].size()*nodes[u].size();
        cnt+=nodes[u].size()*nodes[v].size()*2;

        for (auto cv:in[v]){
            if (in[u].count(cv)) cnt-=nodes[u].size()+nodes[v].size();
            outp[get(cv)].erase(v);
            in[u].insert(cv);
            outp[get(cv)].insert(u);
            // cout << u << ": ";
            // for (auto ch:outp[u]) cout << ch << " ";
            // cout << " || ";
            // cout << get(cv) << "<-" << cv << " so " << outp[u].count(get(cv)) << ln;
            if (outp[u].count(get(cv))) buffer.push({u, cv});
        }
        for (auto cv:outp[v]){
            outp[u].insert(cv);
            if (outp[cv].count(u)) buffer.push({cv, u});
        }
        for (auto cv:nodes[v]) nodes[u].insert(cv);
        // cout << "To: " << cnt << ln;
        nodes[v].clear(); in[v].clear(); outp[v].clear();
    }
    void link(ll u, ll v){
        buffer.push({u, v});
        while (!buffer.empty()){
            tie(u, v) = buffer.front();
            ll pu = get(u), pv=get(v);
            buffer.pop();
            if (pu==pv or (in[pv].count(u) and !outp[pv].count(pu))) continue;
            else if (outp[pv].count(pu)){
                unite(pu, pv);
            }else{
                cnt+=nodes[pv].size();
                outp[pu].insert(pv); in[pv].insert(u);
            }
            // cout << u << " -> " << v << ": " << cnt << ln;
        }
    }
};

void solve(){
    ll n, m; cin >> n >> m;
    DSU tr(n);
    for (ll i=0; i<m; i++){
        ll u, v; cin >> u >> v;
        tr.link(u, v);
        cout << tr.cnt << ln;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) solve();
}

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