Submission #1067271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067271		_8_8_	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	1 / 100	144 ms	65524 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;

int n, m, p[N];
int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
set<int> s[N],g[N],t[N],gr[N];
ll cl(int v) {
    return (int)s[v].size() * 1ll * ((int)s[v].size() - 1);
}
ll d(int v) {
    return (int)s[v].size() * 1ll * (int)t[v].size();
}
ll res = 0;
void merge(int  v,int u) {
    v = get(v);
    u = get(u);
    if(v == u) return;
    res -= cl(v);
    res -= cl(u);
    res -= d(v);
    res -= d(u);
    p[v] = u;
    if((int)s[v].size() > (int)s[u].size()) {
        s[v].swap(s[u]);
    }
    for(int i:s[v]) {
        s[u].insert(i);
        t[u].erase(i);
    }
    for(int i:t[v]) {
        if(s[u].find(i) != s[u].end()) {
            t[u].erase(i);
        } else {
            t[u].insert(i);
        }
    }
    g[u].erase(v);
    g[v].erase(u);
    vector<pair<int,int>> mrg;
    for(int i:g[v]) {
        if(g[i].count(u)) {
            mrg.push_back({i,u});
        }
        g[u].insert(i);
        gr[i].erase(v);
        gr[i].insert(u);
    }
    gr[v].erase(u);
    gr[u].erase(v);
    for(int i:gr[v]) {
        if(g[u].count(i)) {
            mrg.push_back({i,u});
        }
        gr[u].insert(i);
        g[i].erase(v);
        g[i].insert(u);
    }
    res += cl(u);
    res += d(u);
    for(auto [x,y]:mrg) {
        merge(x,y);
    }
}
void test() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        p[i] = i;
        s[i].insert(i);
    }
    for(int tc = 1;tc <= m;tc++) {
        int a,b;
        cin >> a >> b;
        int A = get(a),B = get(b);
        if(A == B || t[B].count(a)) {
            cout << res << '\n';
            continue;
        }
        // cout << A << ' ' << B << '\n';
        // for(int j:g[B]) {
        // }
        if(g[B].count(A)) {
            merge(A,B);
        } else {
            g[A].insert(B);
            gr[B].insert(A);
            t[B].insert(a);
            res += (int)s[B].size();
        }
        cout << res << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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