Submission #1197643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197643		LucaIlie	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	1728 ms	144184 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());
}

vector<pair<int, int>> coada;
void unionn(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    if (u == v)
        return;

    if (vert[u].size() < vert[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]) {
        if (outComponents[u].find(x) != outComponents[u].end())
            coada.push_back({x, u});
    }
    for (int x: outComponents[v]) {
        if (inComponents[u].find(x) != inComponents[u].end())
            coada.push_back({x, u});
    }
    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)) {
                coada.push_back({u, v});
                while (!coada.empty()) {
                    int u = coada.back().first, v = coada.back().second;
                    coada.pop_back();
                    unionn(u, v);
                }
            } else {
                inComponents[pv].insert(pu);
                outComponents[pu].insert(pv);
                if (!isEdgeFromVertexToComponent(u, pv)) {
                    totalEdges += sizee[pv];
                    inVertices[pv].insert(u);
                }
            }
        }

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

    return 0;
}

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