Submission #1245111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245111		bbldrizzy	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	1110 ms	65216 KiB

joitter2

#include <iostream>
#include <vector>
#include <set>
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
ll ans = 0;
vector<set<int>> out;
vector<set<int>> in;
vector<set<int>> ovr;
queue<pair<int, int>> murg;

void con(int A, int B) {
    out[A].insert(B);
    in[B].insert(A);
    if (out[B].count(A)) murg.push({A, B});
}

class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;
  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}

	/** @return the "representative" node in x's component */
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

	/** @return whether the merge changed connectivity */
	void unite(int x, int y) {
        x = find(x); y = find(y);
		if (x == y) { return; }
		if (ovr[x].size()+out[x].size()+in[x].size() < ovr[y].size()+out[y].size()+in[y].size()) { swap(x, y); }
        ans += sizes[x]*ovr[y].size()+sizes[y]*ovr[x].size();
        for (auto sx: ovr[y]) {
            if (ovr[x].count(sx)) {
                ans -= (sizes[x]+sizes[y]);
            } else {
                ovr[x].insert(sx);
            }
        }
        out[x].erase(y);
        out[y].erase(x);
        in[x].erase(y);
        in[y].erase(x);
		sizes[x] += sizes[y];
		parents[y] = x;
        for (auto it: out[y]) {
            in[it].erase(y);
            con(x, it);
        }
        for (auto it: in[y]) {
            out[it].erase(y);
            con(it, x);
        }
	}

	/** @return whether x and y are in the same connected component */
	bool connected(int x, int y) { return find(x) == find(y); }

    int sz(int x) {
        return sizes[x];
    }
};

int main() {
    int n, m; cin >> n >> m;
    DisjointSets dsu(n);
    out.resize(n);
    in.resize(n);
    ovr.resize(n);
    for (int i = 0; i < n; i++) {
        ovr[i].insert(i);
    }
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; --a; --b;
        b = dsu.find(b);
        if (dsu.find(a) != b && !ovr[b].count(a)) {
            ovr[b].insert(a);
            ans += dsu.sz(b);
            a = dsu.find(a);
            con(a, b);
            while (!murg.empty()) {
                auto x = murg.front();
                murg.pop();
                dsu.unite(x.f, x.s);
            }
        }
        cout << ans << "\n";
    }
}

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