Submission #1225126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225126		Gray	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	0 ms	320 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, out;
    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); out.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()+out[u].size()+nodes[u].size()<in[v].size()+out[v].size()+nodes[v].size()) swap(u, v);
        p[v]=u;
        for (auto cv:in[v]){
            out[cv].erase(v); cnt-=nodes[v].size();
            buffer.push({cv, u});
        }
        for (auto cv:out[v]){
            in[cv].erase(v); cnt-=nodes[cv].size();
            buffer.push({u, cv});
        }
        cnt+=nodes[v].size()*(nodes[u].size())*2;
        cnt+=nodes[v].size()*in[u].size();
        for (auto cv:nodes[v]){
            nodes[u].insert(cv);
        }
    }
    void link(ll u, ll v){
        buffer.push({u, v});
        while (!buffer.empty()){
            tie(u, v) = buffer.front();
            u=get(u); v=get(v); buffer.pop();
            if (u==v or out[u].count(v)) continue;
            else if (out[v].count(u)){
                unite(u, v);
            }else{
                cnt+=nodes[v].size();
                out[u].insert(v);
                in[v].insert(u);
            }
        }
    }
};

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: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83