Submission #1197575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197575		LucaIlie	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	5 ms	9792 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> inEdges[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 (inEdges[c].find(v) != inEdges[c].end());
}

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

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

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

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

    totalEdges += (long long)sizee[u] * inEdges[u].size();
    totalEdges += (long long)sizee[u] * (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 (isEdgeFromVertexToComponent(v, pu))
                unionn(u, v);
            else if (!isEdgeFromVertexToComponent(u, pv)) {
                totalEdges += sizee[pv];
                inEdges[pv].insert(u);
            }
        }

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

    return 0;
}

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