제출 #1264001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264001		tvgk	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	346 ms	41184 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 1e5 + 7;

int n, cnt[mxN];
ll ans, dsu[mxN];
queue<ii> q;
map<int, bool> in[mxN];
set<ii> out[mxN];

int Find(int j)
{
    if (dsu[j] < 0)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

void Erase(int u, int v)
{
    //cerr << u << " " << v << '\n';
    ans -= -dsu[v];

    out[Find(u)].erase({v, u});
    in[v].erase(u);
    q.push({u, v});
}

void Union(int u, int v)
{
    if (cnt[u] > cnt[v])
        swap(u, v);

    while (out[u].size())
    {
        ii j = *out[u].begin();
        Erase(j.se, j.fi);
    }

    while (in[u].size())
        Erase((*in[u].begin()).fi, u);

    ans += dsu[u] * dsu[v] * 2;
    ans += in[v].size() * -dsu[u];
    dsu[v] += dsu[u];
    dsu[u] = v;
}

void Add(int u, int v)
{
    v = Find(v);

    if (Find(u) == v || in[v][u])
        return;

    in[v][u] = 1;
    ans += -dsu[v];
    out[Find(u)].insert({v, u});

    cnt[Find(u)]++;
    cnt[Find(v)]++;

    u = Find(u);
    if ((*out[v].lower_bound(ii(u, 0))).fi == u)
        Union(u, v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        dsu[i] = -1;

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        q.push({u, v});

        //cerr << i << '\n';
        while (q.size())
        {
            auto [u, v] = q.front();
            q.pop();
            Add(u, v);
        }

//        for (int i = 1; i <= n; i++)
//            cerr << dsu[i] << " ";
//        cerr << '\n';

        cout << ans << '\n';
    }
}

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