제출 #434411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434411		KoD	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	1 ms	204 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);
    DSU dsu(N);
    long long answer = 0;
    Vec<std::pair<int, int>> merge;
    const auto process = [&] {
        while (!merge.empty()) {
            auto [x, y] = merge.back();
            merge.pop_back();
            x = dsu.find(x);
            y = dsu.find(y);
            if (x == y) {
                continue;
            }
            answer += (long long) dsu.size(x) * dsu.size(y) * 2;
            for (auto &[z, set] : in[y]) {
                if (set.empty() or dsu.find(z)) {
                    continue;
                }
                answer -= (long long) set.size() * dsu.size(y);
                if (!out[x][z].empty()) {
                    answer -= (long long) out[x][z].size() * dsu.size(z);
                    out[x][z].clear();
                    in[z][x].clear();
                    set.clear();
                    out[z][y].clear();
                    merge.emplace_back(x, z);
                } else {
                    for (const auto u : set) {
                        out[z][y].erase(u);
                        if (in[x][z].insert(u).second) {
                            answer += dsu.size(x);
                            out[z][x].insert(u);
                        }
                    }
                    set.clear();
                }
            }
            for (const auto &[z, set] : in[x]) {
                answer += (long long) dsu.size(y) * set.size();
            } 
            for (auto &[z, set] : out[y]) {
                if (set.empty()) {
                    continue;
                }
                if (!out[z][x].empty()) {
                    answer -= (long long) out[z][x].size() * (dsu.size(x) + dsu.size(y));
                    answer -= (long long) set.size() * dsu.size(z);
                    out[z][x].clear();
                    in[x][z].clear();
                    set.clear();
                    in[z][y].clear();
                    merge.emplace_back(x, z);
                } else {
                    for (const auto u : set) {
                        out[x][z].insert(u);
                        in[z][x].insert(u);
                        in[z][y].erase(u);
                    }
                    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][v].empty()) {
                answer -= (long long) out[v][u].size() * dsu.size(u);
                in[u][v].clear();
                out[v][u].clear();
                merge.emplace_back(u, v);
                process();
            } else {
                if (out[u][v].insert(a).second) {
                    in[v][u].insert(a);
                    answer += dsu.size(v);
                }
            }
        }
        print(answer);
        // for (int i = 0; i < N; ++i) {
        //     if (dsu.find(i) == i) {
        //         std::cout << "group" << i << '\n';
        //         std::cout << "in: ";
        //         for (const auto [x, y] : in[i]) {
        //             std::cout << "(" << x << ", " << y.size() << ") ";
        //         }
        //         std::cout << "\n";
        //         std::cout << "out: ";
        //         for (const auto [x, y] : out[i]) {
        //             std::cout << "(" << x << ", " << y.size() << ") ";
        //         }
        //         std::cout << "\n";
        //     }
        // }
    }
    return 0;
}

컴파일 시 표준 에러 (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: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83