Submission #1108464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108464		windowwife	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5041 ms	407000 KiB

joitter2

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e6 + 2, LG = 20, blocksize = 550, inf = 1e18;
int n, m, a, b, par[maxn];
ll res = 0;
set<int> f[maxn], adj[maxn], radj[maxn];
vector<pair<int, int>> cur;
int find_set (int u)
{
    if (par[u] < 0) return u;
    return (par[u] = find_set(par[u]));
}
void union_set (int u, int v)
{
    if (u == v) return;
    if (f[u].size() + adj[u].size() + radj[u].size() < f[v].size() + adj[v].size() + radj[v].size()) swap(u, v);
    res -= 1LL*par[u]*f[v].size() + 1LL*par[v]*f[u].size();
    par[u] += par[v];
    par[v] = u;
    for (int i : f[v])
    {
        if (f[u].find(i) != f[u].end()) res += par[u];
        else f[u].insert(i);
    }
    f[v].clear();
    adj[u].erase(v); radj[u].erase(v);
    adj[v].erase(u); radj[v].erase(u);
    for (int i : adj[v])
    {
        adj[u].insert(i);
        radj[i].insert(u);
        if (radj[u].find(i) != radj[u].end()) cur.push_back({u, i});
    }
    for (int i : radj[v])
    {
        radj[u].insert(i);
        adj[i].insert(u);
        if (adj[u].find(i) != adj[u].end()) cur.push_back({u, i});
    }
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        par[i] = -1;
        f[i].insert(i);
    }
    while (m--)
    {
        cin >> a >> b;
        b = find_set(b);
        if (a == b || f[b].find(a) != f[b].end())
        {
            cout << res << '\n';
            continue;
        }
        res -= par[b];
        f[b].insert(a);
        a = find_set(a);
        adj[a].insert(b);
        radj[b].insert(a);
        if (radj[a].find(b) != radj[a].end()) cur.push_back({a, b});
        while (!cur.empty())
        {
            union_set(cur[0].first, cur[0].second);
            swap(cur[0], cur.back());
            cur.pop_back();
        }
        cout << res << '\n';
    }
}

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