Submission #331996

#	Time	Username	Problem	Language	Result	Execution time	Memory
331996		12tqian	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	1461 ms	44484 KiB

joitter2

#include <bits/stdc++.h>

int main() {
    using namespace std;
    typedef long long ll;
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    vector<int> label(n);
    iota(label.begin(), label.end(), 0);
    vector<int> size(n, 1);    
    vector<set<int>> in(n);
    vector<set<pair<int, int>>> out(n);
    function<int(int)> get = [&](int u) -> int {
        if (label[u] == u) 
            return u;
        return label[u] = get(label[u]);
    };
    function<void(int, int)> direct = [&](int u, int v) {
        int x = get(u);
        int y = get(v);
        if (x == y)
            return;
        auto it = out[y].lower_bound({x, 0});
        if (it != out[y].end() && (*it).first == x) {
            if (in[x].size() + out[x].size() < in[y].size() + out[y].size()) 
                swap(x, y);
            vector<pair<int, int>> vout;
            for (auto& e : out[y]) {
                ans -= size[e.first];
                in[e.first].erase(e.second);
                if (e.first != x) 
                    vout.push_back(e);
            }
            out[y].clear();
            ans += 1LL * size[y] * (2 * size[x] + in[x].size() - in[y].size());
            vector<int> vin;
            for (auto& e : in[y]) {
                int j = get(e);
                out[j].erase({y, e});
                if (j != x)
                    vin.push_back(e); 
            }
            in[y].clear();
            label[y] = x;
            size[x] += size[y];
            for (int& e : vin)
                direct(e, x);
            for (auto& e : vout) 
                direct(e.second, e.first);
        } else if (!in[y].count(u)) {
            ans += size[y];
            in[y].insert(u);
            out[x].insert({y, u});
        }
    };
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        direct(u, v);
        cout << ans << '\n';
    }
    return 0;
}

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