Submission #1175211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175211		nrg_studio	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	499 ms	93196 KiB

joitter2

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

#define ll long long
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define vec vector

const int MAX_N = 1e5;
unordered_set<int> in[MAX_N], out[MAX_N], comp[MAX_N];
ll par[MAX_N], sz[MAX_N];
ll ans = 0;
queue<pair<int,int>> todo;

int get(int x) {return par[x]==x ? par[x] : par[x]=get(par[x]);}

void add(int x, int y) {
    if (out[x].count(y)) {return;} // side case: there already exists an edge between the two components

    out[x].insert(y); // add edge
    in[y].insert(x);
    
    if (out[y].count(x)) {todo.push({x,y});} // if there is a bidirectional edge, merge the components
}

int tot_sz(int x) {return comp[x].size()+in[x].size()+out[x].size();}

void merge(int a, int b) {
    a = get(a); b = get(b);
    if (a==b) {return;}

    ans -= comp[a].size()*sz[a]-sz[a]; // subtract the old answer for this comp;
    ans -= comp[b].size()*sz[b]-sz[b];

    if (tot_sz(a)<tot_sz(b)) {
        swap(a,b);
    }

    in[a].erase(b); out[a].erase(b); // erase the bidirectional edge between the comps;
    in[b].erase(a); out[b].erase(a);

    for (int x : out[b]) { // merge the in and out arrays;
        in[x].erase(b);
        add(a,x);
    }
    for (int x : in[b]) {
        out[x].erase(b);
        add(x,a);
    }

    for (int x : comp[b]) {comp[a].insert(x);} // the comp arrays;
    
    sz[a] += sz[b];
    ans += comp[a].size()*sz[a]-sz[a]; // and add back the new answer for this comp
    par[b] = a;
}


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

    F0R(i,MAX_N) {
        par[i] = i;
        sz[i] = 1;
        comp[i].insert(i);
    }
    int n, m; cin >> n >> m;
    while (m--) {
        int a, b; cin >> a >> b;
        a--; b--;

        if (!comp[get(b)].count(a)) {ans += sz[get(b)];} // edge a->b, so add a to the comp set of b and upd ans
        comp[get(b)].insert(a);
        a = get(a); b = get(b);
        add(a,b); // finally add edge between component of a and component of b

        while (todo.size()) { // todo merge
            merge(get(todo.front().first),get(todo.front().second));
            todo.pop();
        }
        cout << ans << '\n';
    }
}

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