Submission #212760

#	Time	Username	Problem	Language	Result	Execution time	Memory
212760		Alexa2001	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	15 ms	16896 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
const int Nmax = 1e5 + 5;

set<int> in[Nmax], cIn[Nmax], cOut[Nmax];

vector<int> who[Nmax];

int n, m;
int where[Nmax];

ll ans = 0;


ll take2(int x)
{
    return (ll) x * (x-1);
}


void unite(int x, int y)
{
    if(x == y) return;

    if(cIn[x].find(y) == cIn[x].end() || cOut[x].find(y) == cOut[x].end()) return;

    if(who[x].size() + in[x].size() + cIn[x].size() + cOut[x].size() < who[y].size() + in[y].size() + cIn[y].size())
        swap(x, y);

    ans -= take2(who[x].size());
    ans -= take2(who[y].size());
    ans += take2(who[x].size() + who[y].size());

    ans -= (ll) who[x].size() * in[x].size();
    ans -= (ll) who[y].size() * in[y].size();

 //   for(auto it : in[x]) cerr << it << ' '; cerr << "#\n";
  //  for(auto it : in[y]) cerr << it << ' '; cerr << "#\n";

    for(auto it : who[y])
        if(in[x].find(it) != in[x].end())
            in[x].erase(it);

    for(auto it : in[y])
        if(where[it] != x)
            in[x].insert(it);

    for(auto it : who[y])
    {
        who[x].push_back(it);
        where[it] = x;
    }

    for(auto it : cOut[y])
        if(it != x)
        {
            cIn[it].erase(y);
            cIn[it].insert(x);
            cOut[x].insert(it);
        }

    for(auto it : cIn[y])
        if(it != x)
        {
            cOut[it].erase(y);
            cOut[it].insert(x);
            cIn[x].insert(it);
        }

    ans += (ll) who[x].size() * in[x].size();

    for(auto it : cIn[y])
        unite(x, it);

    for(auto it : cOut[y])
        unite(x, it);

    who[y].clear(); in[y].clear(); cIn[y].clear(); cOut[y].clear();
}

void compute(int X, int Y)
{
    int x, y;

    x = where[X];
    y = where[Y];
    if(x == y) return;

    auto itt = in[y].insert(X);
    if(itt.second)
    {
        ans += who[y].size();
        cIn[y].insert(x);
        cOut[x].insert(y);
    }

    unite(x, y);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    for(int i=1; i<=n; ++i)
    {
        where[i] = i;
        who[i].push_back(i);
    }

    for(int i=1; i<=m; ++i)
    {
        int x, y;
        cin >> x >> y;
        compute(x, y);
        cout << ans << '\n';
    }

    return 0;
}

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