Submission #374049

#	Time	Username	Problem	Language	Result	Execution time	Memory
374049		duchung	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	717 ms	41184 KiB

joitter2

#define ii pair<int , int>
#define ll long long

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n , m;
ll ans = 0;
int parent[N];
ll sz[N];
set<ii> edge[N];
set<int> group[N];

int find_set(int u)
{
    return parent[u] == u ? u : find_set(parent[u]);
}

void join(int U , int V)
{
    int u = find_set(U) , v = find_set(V);
    if (u == v) return;

    auto it = edge[v].lower_bound(make_pair(u , 0));
    if (it != edge[v].end() && it->first == u)
    {
        ans += sz[u] * sz[v] * 2;

        if (edge[u].size() + group[u].size() > edge[v].size() + group[v].size()) swap(u , v);

        vector<ii> new_edge;
        for (auto e : edge[u])
        {
            group[e.first].erase(e.second);
            ans -= sz[e.first];
            if (e.first != v) new_edge.push_back(e);
        }

        edge[u].clear();
        ans -= sz[u] * group[u].size();
        ans += sz[u] * group[v].size();

        vector<int> new_group;
        for (auto X : group[u])
        {
            int x = find_set(X);
            edge[x].erase({u , X});
            if (x != v) new_group.push_back(X);
        }

        group[u].clear();
        parent[u] = v , sz[v] += sz[u];
        for (auto e : new_edge) join(e.second , e.first);
        for (auto X : new_group) join(X , v);

    }
    else if (!group[v].count(U))
    {
        ans += sz[v];
        edge[u].emplace(make_pair(v , U));
        group[v].insert(U);
    }

}

int main()
{
    // freopen(".inp","r",stdin);
    // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 1 ; i <= n ; ++i)
    {
        parent[i] = i;
        sz[i] = 1;
    }

    while(m--)
    {
        int U , V;
        cin >> U >> V;
        join(U , V);
        cout << ans << "\n";
    }

}

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