Submission #1151773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151773		12345678	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	560 ms	69756 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

int n, m, a, b, dsu[nx], cnt[nx];
ll res, sz[nx];
set<int> nd[nx], in[nx], ind[nx], outnd[nx];

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void addedge(int a, int b);

void merge(int a, int b)
{
    if (cnt[b]>cnt[a]) swap(a, b);
    res-=sz[a]*(sz[a]-1);
    res-=sz[b]*(sz[b]-1);
    vector<pair<int, int>> edg;
    for (auto u:nd[b])
    {
        for (auto v:outnd[u])
        {
            res-=sz[v];
            ind[v].erase(u);
            if (in[v].find(find(u))!=in[v].end()) in[v].erase(find(u));
            edg.push_back({u, v});
        }
        outnd[u].clear();
    }
    res-=ind[a].size()*sz[a];
    res-=ind[b].size()*sz[b];
    for (auto v:ind[b])
    {
        outnd[v].erase(b);
        edg.push_back({v, b});
    }
    in[b].clear();
    ind[b].clear();
    dsu[b]=a;
    sz[a]+=sz[b];
    cnt[a]+=cnt[b];
    res+=sz[a]*ind[a].size();
    res+=sz[a]*(sz[a]-1);
    for (auto x:nd[b]) nd[a].insert(x);
    nd[b].clear();
    for (auto [u, v]:edg) addedge(u, v);
}

void addedge(int a, int b)
{
    int pa=find(a), pb=find(b);
    if (pa==pb||ind[pb].find(a)!=ind[pb].end()) return;
    if (in[pa].find(pb)!=in[pa].end()) merge(pa, pb);
    else 
    {
        outnd[a].insert(pb);
        cnt[pa]++;
        cnt[pb]+=2;
        ind[pb].insert(a);
        res+=sz[pb];
        in[pb].insert(pa);
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) dsu[i]=i, sz[i]=1, nd[i].insert(i);
    while (m--) cin>>a>>b, addedge(a, b), cout<<res<<'\n';
}

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