제출 #1279317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279317		uranium235	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	1 ms	572 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct state {
    set<int> members;
    map<int, int> inEdges;
    // ll within = 0, inSum = 0;
    void merge(state &x) {
        assert(members.size() >= x.members.size());

        // cout << "premerge " << within << endl;

        for (int i : x.members) {
            map<int, int>::iterator it = inEdges.find(i);
            if (it != inEdges.end()) {
                // within += it->second;
                // inSum -= it->second;
                inEdges.erase(it);
            }
        }

        for (map<int, int>::iterator it = x.inEdges.begin(); it != x.inEdges.end(); it++) {
            // edge from larger to smaller
            if (members.find(it->first) != members.end()) {
                // within += it->second;                
            } else {
                inEdges[it->first] += it->second;
                // inSum += it->second;
            }
        }

        members.insert(x.members.begin(), x.members.end());
        // cout << "postmerge " << endl;
    }
    ll ans() {
        ll sz = members.size();
        return sz * (sz - 1) + inEdges.size() * sz;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<state> states(n);
    for (int i = 0; i < n; i++) states[i].members.insert(i);
    vector<int> parents(n);
    iota(parents.begin(), parents.end(), 0);

    auto par = [&](int v, auto &&self) -> int {
        return parents[v] == v ? v : (parents[v] = self(parents[v], self));
    };

    vector<set<int>> adj(n), radj(n);

    ll ans = 0;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;

        int ar = par(a, par), br = par(b, par);
        ans -= states[ar].ans();
        ans -= states[br].ans();
        if (ar == br) {
            // states[ar].within++;
        } else {
            states[br].inEdges[a]++;
            // states[br].inSum++;
            adj[br].insert(ar);
            radj[ar].insert(br);
        }
        ans += states[ar].ans();
        ans += states[br].ans();
        
        if (adj[ar].find(br) != adj[ar].end()) {
            assert(ar != br);
            if (states[ar].members.size() < states[br].members.size()) swap(ar, br);
            
            ans -= states[ar].ans();
            ans -= states[br].ans();
            parents[br] = ar;
            states[ar].merge(states[br]);
            ans += states[ar].ans();

            for (int j : radj[br]) {
                set<int>::iterator it = adj[j].find(br);
                assert(it != adj[j].end());
                adj[j].insert(ar);
                adj[j].erase(it);
            }
            for (int j : adj[br]) {
                set<int>::iterator it = radj[j].find(br);
                assert(it != radj[j].end());
                radj[j].insert(ar);
                radj[j].erase(it);
            }
            adj[ar].insert(adj[br].begin(), adj[br].end());
            radj[ar].insert(radj[br].begin(), radj[br].end());
            adj[ar].erase(ar);
            radj[ar].erase(ar); 
        }
        // cout << "i " << i << " " << ans << endl;
        cout << ans << '\n';
    }
}

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