Submission #434427

#	Time	Username	Problem	Language	Result	Execution time	Memory
434427		KoD	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	17 / 100	5042 ms	100444 KiB

joitter2

#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

int scan() {
    int x;
    std::scanf("%d", &x);
    return x;
}

void print(const long long x) {
    std::printf("%lld\n", x);
}

struct DSU {
    Vec<int> par;
    DSU(const int n) : par(n, -1) {}
    int find(const int x) {
        return par[x] < 0 ? x : par[x] = find(par[x]);
    }
    int size(const int x) {
        return -par[find(x)];
    }
    void absorb(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            par[x] += par[y];
            par[y] = x;
        }
    }
};

int main() {
    const int N = scan();
    int M = scan();
    Vec<std::map<int, std::set<int>>> in(N), out(N);
    Vec<int> sum(N);
    DSU dsu(N);
    long long answer = 0;
    std::queue<std::pair<int, int>> merge;
    const auto process = [&] {
        while (!merge.empty()) {
            auto [x, y] = merge.front();
            merge.pop();
            x = dsu.find(x);
            y = dsu.find(y);
            if (x == y) {
                continue;
            }
            answer -= (long long) dsu.size(x) * out[y][x].size();
            answer -= (long long) dsu.size(y) * out[x][y].size();
            sum[x] -= in[x][y].size();
            in[x].erase(y);
            sum[x] -= out[x][y].size();
            out[x].erase(y);
            sum[y] -= in[y][x].size();
            in[y].erase(x);
            sum[y] -= out[y][x].size();
            out[y].erase(x);
            if (sum[y] > sum[x]) {
                std::swap(x, y);
            }
            answer += (long long) dsu.size(x) * dsu.size(y) * 2;
            for (auto &[z, set] : in[y]) {
                assert(!set.empty());
                answer -= (long long) set.size() * dsu.size(y);
                if (out[x].find(z) != out[x].end()) {
                    merge.emplace(x, z);
                }
                for (const auto u : set) {
                    if (in[x][z].insert(u).second) {
                        sum[x] += 1;
                        sum[z] += 1;
                        answer += dsu.size(x);
                        out[z][x].insert(u);
                    }
                }
                sum[z] -= out[z][y].size();
                out[z].erase(y);
                set.clear();
            }
            for (const auto &[z, set] : in[x]) {
                answer += (long long) dsu.size(y) * set.size();
            } 
            for (auto &[z, set] : out[y]) {
                assert(!set.empty());
                if (out[z].find(x) != out[z].end()) {
                    merge.emplace(x, z);
                }
                for (const auto u : set) {
                    sum[x] += 1;
                    sum[z] += 1;
                    out[x][z].insert(u);
                    in[z][x].insert(u);
                }
                sum[z] -= in[z][y].size();
                in[z].erase(y);
                set.clear();
            }
            dsu.absorb(x, y);
        }
    };
    while (M--) {
        const int a = scan() - 1;
        const int b = scan() - 1;
        const int u = dsu.find(a);
        const int v = dsu.find(b);
        if (u != v) {
            if (in[u].find(v) != in[u].end()) {
                merge.emplace(u, v);
                process();
            } else {
                if (out[u][v].insert(a).second) {
                    sum[u] += 1;
                    sum[v] += 1;
                    in[v][u].insert(a);
                    answer += dsu.size(v);
                }
            }
        }
        print(answer);
    }
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int scan()':
joitter2.cpp:7:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     std::scanf("%d", &x);
      |     ~~~~~~~~~~^~~~~~~~~~

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