Submission #1197619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197619		LucaIlie	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	9 ms	19012 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
long long totalEdges = 0;
int parent[MAX_N + 1], sizee[MAX_N + 1];
set<int> inVertices[MAX_N + 1], inComponents[MAX_N + 1], outComponents[MAX_N + 1];
set<int> vert[MAX_N + 1];

int findParent(int u) {
    if (parent[u] != u)
        parent[u] = findParent(parent[u]);
    return parent[u];
}

bool isEdgeFromVertexToComponent(int v, int c) {
    return (inVertices[c].find(v) != inVertices[c].end());
}

bool isEdgeFromComponentToComponent(int u, int v) {
    return (inComponents[v].find(u) != inComponents[v].end());
}

void unionn(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    if (u == v)
        return;

    if (inVertices[u].size() < inVertices[v].size())
        swap(u, v);

    totalEdges -= (long long)sizee[u] * (inVertices[u].size() + sizee[u] - 1);
    totalEdges -= (long long)sizee[v] * (inVertices[v].size() + sizee[v] - 1);

    parent[v] = u;
    sizee[u] += sizee[v];
    for (int x: vert[v]) {
        vert[u].insert(x);
        inVertices[u].erase(x);
    }
    vert[v].clear();
    for (int x: inVertices[v]) {
        if (vert[u].find(x) == vert[u].end())
            inVertices[u].insert(x);
    }
    inVertices[v].clear();

    for (int x: inComponents[v]) {
        inComponents[u].insert(x);
        outComponents[x].insert(u);
    }
    for (int x: outComponents[v]) {
        outComponents[u].insert(x);
        inComponents[x].insert(u);
    }

    totalEdges += (long long)sizee[u] * (inVertices[u].size() + sizee[u] - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int v = 1; v <= n; v++) {
        parent[v] = v, sizee[v] = 1;
        vert[v].insert(v);
    }

    totalEdges = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        int pu = findParent(u);
        int pv = findParent(v);

        if (pu != pv) {
            if (isEdgeFromComponentToComponent(pv, pu))
                unionn(u, v);
            else {
                inComponents[pv].insert(pu);
                outComponents[pu].insert(pv);
                if (!isEdgeFromVertexToComponent(u, pv)) {
                    totalEdges += sizee[pv];
                    inVertices[pv].insert(u);
                }
            }
        }

        totalEdges = 0;
        for (int u = 1; u <= n; u++) {
            if (findParent(u) != u)
                continue;

            totalEdges += (long long)sizee[u] * (inVertices[u].size() + sizee[u] - 1);
            /* if (i == 7) */
            /*     printf("%d %d %d\n", u, sizee[u], (int)inVertices[u].size()); */
        }

        cout << totalEdges << "\n";
    }

    return 0;
}

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