Submission #1158852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158852		ace5	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	295 ms	45868 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<set<int>> ine; //vertices
vector<set<int>> oute; //components
vector<vector<int>> comp;
vector<int> mycomp;
deque<pair<int,int>> to_mrg;

ll ans = 0;

ll func(int v)
{
    ll k = ine[v].size();
    ll szc = comp[v].size();
    return k * szc + szc*(szc-1);

}

void mrg()
{
    int u = mycomp[to_mrg[0].first];
    int v = mycomp[to_mrg[0].second];
    to_mrg.pop_front();
    if(u == v)
        return ;
    ans -= func(u);
    ans -= func(v);
    if(ine[u].size()+oute[u].size()+comp[u].size() > ine[v].size()+oute[v].size()+comp[v].size())
        swap(u,v);
    for(auto c:ine[u])
    {
        if(mycomp[c] != v)
        {
            if(oute[v].find(mycomp[c]) != oute[v].end())
            {
                to_mrg.push_back({v,mycomp[c]});
            }
            ine[v].insert(c);
            oute[mycomp[c]].erase(u);
            oute[mycomp[c]].insert(v);
        }
    }
    for(auto c:oute[u])
    {
        if(c != v)
        {
            oute[v].insert(c);
            if(oute[c].find(v) != oute[c].end())
            {
                to_mrg.push_back({v,c});
            }
        }
    }
    oute[v].erase(u);
    for(auto c:comp[u])
    {
        ine[v].erase(c);
        comp[v].push_back(c);
        mycomp[c] = v;
    }
    ine[u].clear();
    oute[u].clear();
    comp[u].clear();
    ans += func(v);
    return ;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    ine.resize(n);
    oute.resize(n);
    comp.resize(n);
    mycomp.resize(n);
    for(int j = 0;j < n;++j)
    {
        mycomp[j] = j;
        comp[j].push_back(j);
    }
    for(int j = 0;j < m;++j)
    {
        int u,v;
        cin >> u >> v;
        int u2 = u-1;
        u--;
        v--;
        u = mycomp[u];
        v = mycomp[v];
        if(u == v)
        {
            cout << ans << "\n";
            continue;
        }
        ans -= func(v);
        ine[v].insert(u2);
        oute[u].insert(v);
        ans += func(v);
        if(oute[v].find(u) != oute[v].end())
        {
            to_mrg.push_back({u,v});
            while(to_mrg.size())
                mrg();
        }
        cout << ans << "\n";
    }
}

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