Submission #1216874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216874		vanea	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	4 ms	9792 KiB

joitter2

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

const int mxN = 1e5+10;

ll ans = 0, cnt = 0;
int p[mxN];
multiset<int> rev_adj[mxN], rev_adj1[mxN];

int get(int x) {
    return p[x] < 0 ? x : p[x] = get(p[x]);
}

void uni(int p1, int p2) {
    ll sz1 = -(p[p1]), sz2 = -(p[p2]);
    ll now = sz1 * (sz1 - 1) + sz2 * (sz2 - 1);
    now += ((ll)rev_adj[p1].size()) * sz1;
    now += ((ll)rev_adj[p2].size()) * sz2;
    ans -= now;
    if(rev_adj[p1].size() < rev_adj[p2].size()) swap(p1, p2);
    for(auto it : rev_adj[p2]) if(it != p1) rev_adj[p1].insert(it);
    for(auto it : rev_adj1[p2]) rev_adj1[p1].insert(it);
    rev_adj[p1].erase(p2);
    rev_adj1[p2].clear();
    rev_adj[p2].clear();
    p[p1] += p[p2];
    p[p2] = p1;
    sz1 += sz2;
    ans += sz1 * (sz1 - 1);
    ans += sz1 * (ll)(rev_adj[p1].size());
}

void add_leaf(int a, int b) {
    int p1 = get(a), p2 = get(b);
    if(p1 == p2) return ;
    auto it1 = rev_adj1[p2].find(a);
    if(it1 != rev_adj1[p2].end()) return ;
    auto it = rev_adj[p1].find(p2);
    if(it != rev_adj[p1].end()) uni(p1, p2);
    else {
        rev_adj[p2].insert(p1);
        rev_adj1[p2].insert(a);
        ans += (ll)(-p[p2]);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        p[i] = -1;
    }
    while(m--) {
        int a, b;
        cin >> a >> b;
        add_leaf(a, b);
        ++cnt;
        cout << ans << '\n';
    }
    return 0;
}

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