Submission #1014428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014428		codefox	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	0 ms	348 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

vector<int> rep;
vector<set<int>> repgraph;
vector<set<int>> revgraph;
vector<long long> rsize;
vector<vector<int>> rin;

long long sol = 0;

int finde(int i)
{
    if (i != rep[i]) rep[i] = finde(rep[i]);
    return rep[i];
}

int main()
{
    int n, m;
    cin >> n >> m;
    rep.resize(n);
    repgraph.assign(n, set<int>());
    revgraph.assign(n, set<int>());
    rin.assign(n, vector<int>());
    rsize.assign(n, 1);
    iota(rep.begin(), rep.end(), 0);
    for (int i = 0; i < n; i++)
    {
        rin[i].push_back(i);
    }

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (finde(a)==finde(b))
        {
            cout << sol << "\n";
            continue;
        }
        if (repgraph[finde(b)].find(finde(a))==repgraph[finde(b)].end())
        {
            //a is not contained in graph from b;
            //connect a to all nodes in b
            sol -= rsize[finde(b)]*revgraph[finde(b)].size();
            repgraph[finde(a)].insert(finde(b));
            revgraph[finde(b)].insert(a);
            sol += rsize[finde(b)]*revgraph[finde(b)].size();
            cout << sol << "\n";
            continue;
        }
        queue<int> q;
        q.push(a);
        while (q.size())
        {
            a = q.front();
            q.pop();
            if (finde(a)==finde(b)) continue;
            if (repgraph[finde(a)].size()>repgraph[finde(b)].size())
            {
                //swap(a, b);
            }
            sol -= revgraph[finde(a)].size()*rsize[finde(a)];
            sol -= revgraph[finde(b)].size()*rsize[finde(b)];
            for (int ele:repgraph[a])
            {
                if(finde(ele)==finde(b)) continue;
                repgraph[finde(b)].insert(ele);
            }
            if (rin[finde(a)].size() > rin[finde(b)].size())
            {
                //swap(a, b);
            }
            for (int ele:rin[finde(a)])
            {
                rin[finde(b)].push_back(ele);
                revgraph[finde(b)].erase(ele);
            }
            if (revgraph[finde(a)].size()>revgraph[finde(b)].size())
            {
                //swap(repgraph[finde(a)], repgraph[finde(b)]);
                //swap(a, b);
            }
            for (int ele:revgraph[finde(a)])
            {
                repgraph[finde(ele)].erase(finde(a));
                if (repgraph[finde(b)].find(finde(ele))!= repgraph[finde(b)].end()) q.push(ele);
                else if (finde(ele) != finde(b))
                {
                    repgraph[finde(ele)].insert(finde(b));
                    revgraph[finde(b)].insert(ele);
                }
            }
            sol += rsize[finde(a)]*rsize[finde(b)]*2;
            int sum = rsize[finde(a)]+rsize[finde(b)];
            rsize[finde(a)] = sum;
            rsize[finde(b)] = sum;
            rep[finde(a)] = rep[finde(b)];
            sol += revgraph[finde(b)].size()*rsize[finde(b)];
        }
        cout << sol << "\n";
    }

    return 0;
}

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