Submission #387284

#	Time	Username	Problem	Language	Result	Execution time	Memory
387284		cheissmart	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	2185 ms	107416 KiB

joitter2

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") ->" << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;

set<int> G[N], rG[N], ch[N];
int p[N], sz[N];
queue<pi> q;
ll ans = 0;

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void add_edge(int u, int v) {
    G[u].insert(v);
    rG[v].insert(u);
    if(G[v].count(u)) {
        q.push({u, v});
    }
}

int get_size(int u) {
    return G[u].size() + rG[u].size() + ch[u].size();
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(get_size(x) > get_size(y)) swap(x, y);
    ans += (ll) sz[x] * ch[y].size() + (ll) sz[y] * ch[x].size();
    p[x] = y;
    sz[y] += sz[x];
    // merge x into y
    for(int i:ch[x]) {
        if(ch[y].count(i)) ans -= sz[y];
        else ch[y].insert(i);
    }
    G[x].erase(y), G[y].erase(x);
    rG[x].erase(y), rG[y].erase(x);
    for(int i:G[x]) {
        G[y].insert(i);
        add_edge(y, i);
    }
    for(int i:rG[x]) {
        rG[y].insert(i);
        add_edge(i, y);
    }
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        p[i] = i, sz[i] = 1;
        ch[i].insert(i);
    }
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        v = find(v);
        if(find(u) != v && ch[v].count(u) == 0) {
            ch[v].insert(u);
            ans += sz[v]; // u will connect to everyone in v's component
            u = find(u);
            add_edge(u, v);
            while(q.size()) {
                pi p = q.front(); q.pop();
                unite(p.F, p.S);
            }
        }
        cout << ans << '\n';
    }

}

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