제출 #211932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211932		qkxwsm	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	18 ms	16768 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 100013;

int N, M;
int dsu[MAXN], siz[MAXN];
vi edge[MAXN];
ll ans;

set<pii> out[MAXN]; //vertices coming out of i.
set<int> in[MAXN]; //vertices coming into clique i.
map<int, int> cl[MAXN]; //edges between cliques

void merge(int u, int v);

int get(int u)
{
    return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
void addedge(int u, int v)
{
    // cerr << "addedge " << u << ' ' << v << endl;
    int x = get(u), y = get(v);
    if (x == y || out[x].find({u, y}) != out[x].end())
    {
        //do nothing.
    }
    else if (cl[x].find(y) != cl[x].end() || cl[y].find(x) == cl[y].end())
    {
        // cerr << x << " joins " << y << endl;
        cl[x][y]++;
        ans += siz[y];
        out[x].insert({u, y});
        in[y].insert(u);
    }
    else
    {
        //added an edge from y to x
        merge(x, y);
        //fuck, merge.
    }
}
void merge(int u, int v)
{
    // cerr << "merge " << u << ' ' << v << endl;
    //v -> u is connected, connect u -> v now.
    cl[v].erase(u);
    ans += 2ll * siz[u] * siz[v];
    if (SZ(in[v]) + SZ(out[v]) > SZ(in[u]) + SZ(out[u]))
    {
        swap(u, v);
    }
    //todo some swap.
    for (auto a : out[v])
    {
        if (a.se != u)
        {
            out[u].insert(a);
        }
        else
        {
            in[u].erase(a.fi);
            ans -= siz[u];
        }
    }
    out[v].clear();
    ans += siz[v] * (SZ(in[u]));
    vpi merges;
    for (int w : in[v])
    {
        //if w -> u exists, just dw about it.
        out[get(w)].erase({w, v});
        if (in[u].find(w) != in[u].end())
        {
            //do nothing.
        }
        //if u -> w exists, this prompts another merge.
        else if (cl[u].find(get(w)) != cl[u].end())
        {
            merges.PB({get(w), u});
        }
        //if neither, then w -> v.
        else
        {
            ans += siz[u];
            in[u].insert(w);
            out[get(w)].insert({w, u});
            cl[get(w)].erase(v);
            cl[get(w)][u]++;
        }
    }
    in[v].clear();
    dsu[v] = u;
    siz[u] += siz[v];
    siz[v] = 0;
    sort(ALL(merges));
    merges.erase(unique(ALL(merges)), merges.end());
    for (pii p : merges)
    {
        merge(p.fi, p.se);
    }
    return;
    //the how many people have edges into v or edges into u?
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    FOR(i, 0, N)
    {
        dsu[i] = i;
        siz[i] = 1;
    }
    //store edges of the form clique -> node. they are actually reverses of the actual edges.
    //also, store clique -> clique edges.
    FOR(i, 0, M)
    {
        int u, v;
        cin >> u >> v; u--; v--;
        addedge(u, v);
        cout << ans << '\n';
        //check if u has an edge to anything in v.
    }
    return 0;
}

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